News for hackers. Stuff that matters.

A comment on B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees. Parent comment

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 ]