Initial filesystem design synopsis - indexing

[Matthew Dillon]

: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
:>     them.
:
:Yeah, B+ trees are a proven technology for indexes on slow media.
:
:Cheers,
:-- 
:         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.

						-Matt