Messages in this thread |  | | Date | Fri, 26 Jul 1996 06:05:47 -0400 | From | Mike Black <> | Subject | Re: Is any file system on Linux appropriate for very large directories? |
| |
At 05:00 PM 7/25/96 +0100, Matthias Urlichs wrote: >In linux.dev.kernel, article <199607241957.MAA06475@muddcs.cs.hmc.edu>, > "Michael J. Micek" <mmicek@muddcs.cs.hmc.edu> writes: >> >> Copious information about skiplists is to be found at >> >> ftp://ftp.cs.umd.edu/pub/skipLists >> >There's a big problem with skip lists -- they distribute all their data all >over the place. B*-trees have much better locality. > >Using a skip list, you have to follow the chain of entries on each level to >find out whether you need to continue, or whether you can proceed to the >next level. Each follow-the-link, including the last (where you read data >you can't really use), is one disk read because the entries are rather >unlikely to be colocated. > >With a B* tree, you need to do exactly one read operation per level, and >the higher levels are likely to be in cache anyway. > >My conclusion, therefore, is that a skip list is a rather stupid idea when >you try to apply it to the directory of an on-disk file system. >
I guess I may have to go back and re-do my study for query operations too. My previous testing on skiplists vs b-trees showed skiplists outperformed b-trees on inserts by a factor of 6 or so and several orders of magnitude faster at large numbers of inserts. B* trees are horrible at large numbers of inserts due to rebalancing (which is completely different cache behaviour). I would think on a news server that nightly cleanup would be a real pain due to the number of rebalances that would occurr when removing tens-of-thousand nodes. Somewhere in here we need to balance insert/query operations.
P.S. What was the new mailing list for this subject??? I lost the mail... - /----------------------------------------------------------\ | Mike Black mblack@csihq.com 407-676-5118, x203 | | Computer Science Innovations, Inc. 407-676-2355 FAX | | Melbourne FL 32904-2314 http://www.csihq.com | \----------------------------------------------------------/
|  |