3 ms·
"40% faster?" Sure, but the original code doesn't make much sense. The whole purpose of a B-tree is that you store the keys in a contiguous array to take advant
by judofyr 4y ago
"40% faster?" Sure, but the original code doesn't make much sense. The whole purpose of a B-tree is that you store the keys in a contiguous array to take advantage of locality. If you're going to spread your data around behind pointers you're better suited using a node-based balanced binary search tree (red-black tree, AVL, treap).
This is of course still very exciting to see though! It's a great demonstration that there's some data structures that was impossible to implement properly (and generically) without native support in the language.
- benhoyt 4y agoHuh, today I learned that there's a difference between a B-tree and a binary (search) tree, or at least, that the B-tree is a generalization of a binary tree where the nodes have multiple elements for efficiency. I'd always thought B-tree was just short for "binary tree".
- dataflow 4y agoYup, there are also B+ and B* trees!
- PeterCorless 4y agoWe have a nice blog on that: The Taming of the B-Trees https://www.scylladb.com/2021/11/23/the-taming-of-the-b-trees/ https://www.scylladb.com/2021/11/23/the-taming-of-the-b-tree... "B+-trees have been supported since ScyllaDB Open Source 4.3, and our B-tree implementation was added in release 4.5. They are hidden, under-the-hood optimizations ScyllaDB users benefit from as we continue to evolve our infrastructure."
- nanidin 4y agoHehehe, after reading this post I dug through my college projects to find my B+ tree implementation
- dataflow 4y agoI assume that was a "B+ tree" implementation and not a B+ "tree implementation"... :-)
- deleted 4y ago[deleted]
- DeathArrow 4y ago> It's a great demonstration that there's some data structures that was impossible to implement properly (and generically) without native support in the language. Go's purpose is to be easy to learn, not to write high performance code.