Replace flexible arrays with unsorted b+trees?

Posted Aug 7, 2009 19:07 UTC (Fri) by zlynx (guest, #2285)
Parent article: Flexible arrays

Just an idea, but large parts of B+ tree implementation are similar to flexible arrays / dequeues, except that B+ trees are sorted and can have a tree depth deeper than 1.

I believe the Linux recently got a B+ tree implementation. I wonder if it would be possible to divide that into parts so that node handling, insert, delete and linear traversal code could be shared.

It's probably not worthwhile, but I think it'd be interesting to investigate.

Replace flexible arrays with unsorted b+trees?

Posted Aug 7, 2009 19:12 UTC (Fri) by johill (subscriber, #25196) [Link] (1 responses)

I worked on the b+tree implementation for a while, and then we measured it but it turned out to be slower than using an rbtree, for some reason, so I don't think the b+tree got into the tree at this point. I might be wrong and have missed that tho.

Replace flexible arrays with unsorted b+trees?

Posted Aug 20, 2009 18:29 UTC (Thu) by mfedyk (guest, #55303) [Link]

I believe the OP was referring to btrfs which uses a modified b+tree structure.

Also NTFS, ReiserFS, NSS, XFS, and JFS use B+trees. I wonder if it has been implemented in a library or if there are 5 or 6 differing implementations of b+trees in the kernel...