Initial filesystem design synopsis - indexing
dillon at apollo.backplane.com
Mon Feb 26 10:57:59 PST 2007
:Matthew Dillon wrote:
:> My intention is to use a radix of either 8 or 16, depending on how the
:Order ;). Do you intend to allocate the leaf nodes right after eachother
:as well, to take the most advantage of the linked list behavour
:(assuming the trees grow large)?
:> are basically I/O bound entities. I had very good luck using this
:> sort of structure in the Backplane Database so I am fairly confident
:> that it will scale even unto directories with millions of files in
:Yeah, B+ trees are a proven technology for indexes on slow media.
: Thomas E. Spanjaard
: tgen at netphreax.net
Yah, order 8 or 16. Same difference, really, though I guess 'radix'
implies chopping up bits which is not what you do in a B+Tree.
On the storage.... yah. There's no point reserving data space for
one B+Tree node at a time. It will be chunked up probably in blocks
of 4-8 B+Tree nodes (x order 8 or 16). Performance reorganizations
of the segment will take care of any long term fragmentation.
The nice thing about this is that the B+Tree nodes can be asynchronously
updated... no ordered disk writes are required at all. If a segment
is found to be marked open after a crash the OS will simply regenerate
the B+Tree(s) for that segment from scratch. That's the best of all
possible scenariors for updating indexes.
More information about the Kernel