B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees

Re:B-Trees Require Fewer Comparisons Than Balanced Binary Se... by whizzter on Monday June 24, 2024 @01:16PM (#40778536)

Insertion in AVL tree's is fairly simple and doesn't really have any cascades so they are quite predictable, deletions on the other hand cascades upwards with a bunch of different imbalances and thus rotations(and post rotation balances) to be accounted for.

Recently implemented them for an advanced hobby project and having a solid fuzzing tester in place really alleviated a lot of headaches in the long term since it was able to produce quite an exhaustive set of conditions.

[ Parent | on HN ]

Re:B-Trees Require Fewer Comparisons Than Balanced Binary Se... by nayuki on Monday June 24, 2024 @01:25PM (#40778627)

B-tree deletions are quite complicated too, requiring stealing keys from either-side sibling or merging with either-side sibling.

In practice, I find that a B-tree implementation is 2 to 3× the length of an AVL tree impl.

I also fuzz-tested my implementations thoroughly. https://www.nayuki.io/page/avl-tree-list , https://www.nayuki.io/page/btree-set , etc.

[ Parent | on HN ]

Re:B-Trees Require Fewer Comparisons Than Balanced Binary Se... by DanielHB on Monday June 24, 2024 @03:50PM (#40779919)

Yeah, this is what I was thinking too. The rebalancing on AVL is a bit tricky but once you grok it, it is not that much code...

[ Parent | on HN ]