Exploring the design space of binary search trees

I started this project many years ago when I was coming up with ideas for immutable data structures for the PHP data structures extension [1]. I wanted to support access by position in a sorted set, which led to the idea of using binary search trees for both lists and sets. However, I did not expect the scope of this project to increase as much as it did.

The more I read about binary search trees, the more I thought about them, and so down the rabbit hole I went. When you read everything you can find about a topic for several years, eventually you develop a deep enough understanding to compose new ideas from different sources.

This project is the result of many rejected ideas and countless experiments. I tried my best to distill everything I consider important enough to keep, and will continue to develop other ideas as they come along. I had no intention to implement anything other than weight-balanced strategies to support positional access, but when I read about rank-balanced trees I knew I had to take on the challenge to implement them.

I've been in contact with various authors along the way, specifically Bob Tarjan and Salvador Roura, but have otherwise not received any feedback yet. Implementing all the algorithms was incredibly hard work, by far the hardest work I've ever done, so I hope that others may find value in their presentation.

There is still so much work that could be done, but there comes a time when working on something alone begins to yield diminishing returns. I hope to continue this project as an open-source collaborative effort, so please feel free to ask questions or suggest changes, however small.

[1] https://github.com/php-ds/ext-ds

Exploring the design space of binary search trees
rtheunissen.github.io

That is true, but in a persistent setting they likely also copy more data, and iterator invalidation might be a concern in some cases when moving values around within a B-tree node. The motivation was not really to come up with the best tree structure or to even consider memory hierarchy at all.

Instead, within just the scope of binary search trees specifically, what cool things might we uncover by taking a closer look? In a hypothetical future, our hardware might be so different and caches so large and advanced that the best practices of today might not apply all the same.

Binary search trees today are probably only viable for absolutely massive collections, and at that scale there is almost definitely a better, bespoke solution available. Exploring without necessarily thinking about the hardware, in the abstract, has been a fun sandbox to play in. The fact that we still teach them suggests that they provide value beyond practical application.

Thank you for your feedback, you are absolutely right. In most practical use-cases today, a B-tree would likely achieve better results.

by 'bst laid out in a flat array' i am guessing you mean a layout like a traditional binheap, so, for the keys 1 2 3 4 5 6 7

    4 2 6 1 3 5 7

is that right, and do you mean to make this arbitrarily large

i feel like this is less cache friendly than a naive b-tree, even without rebalancing; if your cache line size is 128 bytes, your keys are 4 bytes, and your b-tree nodes are 15 keys and 16 (4-byte!) pointers, you can reach any of 1048576 keys in 5 cache-line fills, of which probably 2 were already in your cache so it's really 3. by contrast, the flat-array binary search tree above is 20 levels deep. the first 5 levels are in one cache line (because you don't waste any space on pointers) but every key in the following 15 levels of the tree is in its own cache line so you have probably 14 cache-line fills

14 is like a lot more than 3 in my mind maybe

conceivably you have done this in practice and can tell me what i'm overlooking

I believe yes, as illustrated in [1]. This idea only works in a static sense, because to insert a value suffers from the same linear movement of memory as dynamic arrays. B-trees are somewhere in-between because they support logarithmic insert/split/join and make better use of cache than BSTs, a well known fact.

I tried to focus specifically on BSTs in the context of online persistence and concurrency, where they are particularly effective at very large sizes. There is a section on the paper that mentions B-trees but I did not want to include a direct comparison as part of the scope. Take the best candidate from this set, and compare against a good B-tree implementation in whatever situation you might require them.

[1] https://algorithmica.org/en/eytzinger