| |||||||||||||
Replace flexible arrays with unsorted b+trees?Replace flexible arrays with unsorted b+trees?Posted Aug 7, 2009 19:07 UTC (Fri) by zlynx (subscriber, #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.
(Log in to post comments)
Replace flexible arrays with unsorted b+trees? Posted Aug 7, 2009 19:12 UTC (Fri) by johill (subscriber, #25196) [Link]
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...
|
|||||||||||||