A B+Tree is possible.  I am not familiar with a B#Tree but if you mean
    the variation where a node is split before it becomes full instead of
    when it becomes full (which can improve performance when nodes are
    individually locked), then that is a possibility too.

    The issue with a B+Tree verses a B-Tree is that there needs to be
    sufficient space in the B+Tree node to be able to store both record
    information and the pointer to the next BxTree layer.  It turns out
    that we barely have enough space in the current structural design

    It will be cluster-by-cluster to begin with.  I don't expect it to cause
    any issues, the BxTree in each cluster will be fairly compact and well
    cached and, most importantly, nearly all write I/O can be asynchronous
    so locks simply will not be held all that long.

    Eventually it will be possible to use inherent buffer cache locks to
    lock the BxTree operations but its a little dicey to try to do
    that level of fine-grained locking by default due to the allocation
    model.

					-Matt
					Matthew Dillon 
					<dillon@backplane.com>

Anyone up on ReiserFS ?

(but still capable of a 'clean room' description :)

As I recall, according to their docs it seems to have been one of the
first to use BTrees in the general sense for internal structuring ..

also as I recall, there were some performance problems in specific areas
of requiring extra CPU for basic IO (due to having to compute tree
operations rather than do simple pointer manipulations) and also
concurrent IO (due to the need for complex tree locking types of things,
possibly compounded by the extra cpu time)

this kind of a thing is more for replication than 100% raw speed, but
in any case.. just some topics for discussion I suppose ..

I still need to read the more detailed commits.

looking forward to it.

- Chris