40 ms·

Counted B-Trees (2017)

98 points by zerojames 2y ago

EdSchouten 2y ago
This approach is essentially what is called an "augmented data structure". Namely, in this case a B-tree is augmented to store an element count. But there are obviously many other data structures to which this can be applied, and many types of additional values that can be stored. https://www.geeksforgeeks.org/introduction-to-augmented-data-structure/ https://www.geeksforgeeks.org/introduction-to-augmented-data... https://tildesites.bowdoin.edu/~ltoma/teaching/cs231/fall09/Lectures/10-augmentedTrees/augtrees.pdf https://tildesites.bowdoin.edu/~ltoma/teaching/cs231/fall09/... https://www.cs.toronto.edu/~tabrown/csc263/2014W/week4.interval.pdf https://www.cs.toronto.edu/~tabrown/csc263/2014W/week4.inter...
cb321 2y ago
Some here are questioning the motivation of this data structure. It is well motivated at least in the context of time series. We (almost) all learn 2 things at very young ages: 1) the world changes and 2) even one wild point can pollute an average. In time series contexts, we also learn early solutions to 1) a moving data window (flat or fancily weighted over time) and 2) percentiles/quantiles/order statistics are more robust. Combining the two solutions means you want to efficiently delete old/insert new/query quantiles over moving data windows. If you need multiple (e.g. 1%, 25%, median, 75%, 99% is a classic case) and exact quantiles over large data windows (in numbers of points), a counted B-tree is about as good as you can do, and can be many orders of magnitude less work than more naive solutions (which absolutely show up In The Wild - I have personally seen them many times). There is a case that article does not address when you have many-way ties aka many duplicate keys, but that can be handled within the same general framework. If you know something about the dynamic range of your data then you can also get more approximate dynamic quantiles with a histogram with log/exp-spaced bins (like floats) with counters backed by a Fenwick Tree (to make both PDF & CDF updates efficient). You can further boost accuracy with Parzen mid-quantile interpolation. A fully worked example in Nim is at https://github.com/c-blake/adix/blob/master/adix/lghisto.nim https://github.com/c-blake/adix/blob/master/adix/lghisto.nim In the same github repo there is also a Nim implemention of counted B-trees (though it is harder to use).
- kragen 2y ago
  this is an excellent example of when you'd want to use counted b-trees, but much more generally, they provide a middle ground between arrays and linked lists in arrays, indexing is fast (one instruction), but insertion and deletion is slow in linked lists, indexing is slow, but insertion and deletion are fast (≈10 instructions) (iteration is fast in both, though on modern cpus you have to store multiple items per linked-list node for that to remain true) in counted b-trees, both indexing and insertion/deletion are fast, though not as fast as in arrays or linked lists: logarithmic time instead of constant time, with a larger constant factor
muizelaar 2y ago
Does anyone know of a persistent/on-disk implementation of this kind of data structure?
- deleted 2y ago
  [deleted]
nayuki 2y ago
The order statistic tree was covered in the CLRS book. In the 4th edition, it is chapter 17 "Augmenting Data Structures", subchapter 1 "Dynamic order statistics". (I know for a fact it was present in the 3rd and 2nd editions too; did not check the 1st.) I used this knowledge to implement a tree-based list data structure, with no set functionality at all: https://www.nayuki.io/page/avl-tree-list https://www.nayuki.io/page/avl-tree-list
- cb321 2y ago
  By separating "seek" (min/max/key/nth) from "edit" (in-del) and "balance" (AVL, red-black, etc.) operations, you can indeed cover a lot of bases as elaborated here: https://github.com/c-blake/bst https://github.com/c-blake/bst (including also how you handle duplicate keys as well as the perhaps less useful neither-ranked-nor-keyed access, wherein the trees are kind of a double-ended queue with just "edge access").
  - turndown 2y ago
    >perhaps less useful neither-ranked-nor-keyed access, wherein the trees are kind of a double-ended queue with just "edge access" For normal btrees this is absolutely true. For b+trees you will see this basically everywhere.
samsquire 2y ago
I've been interested in this data structure for the ability to scan forward efficiently to any depth. I am thinking of a binary protocol that can be navigated extremely efficiently and also be inserted into at any depth.
tidwall 2y ago
A working example in Go. https://github.com/tidwall/btree https://github.com/tidwall/btree
James_K 2y ago
Good examples of this would be the "rope" used in various text editors and Clojure's persistent vector data type.
kragen 2y ago
probably if you like this data structure you will want to read raph levien's extensive treatise on its many variations and applications, specifically with respect to writing text editors, entitled "rope science": https://xi-editor.io/docs/rope_science_00.html https://xi-editor.io/docs/rope_science_00.html
kazinator 2y ago
Scapegoat trees make use of subtree counts. But, according to Rivest's description of the algorithm, they are not stored; the counts are dynamically calculated when needed. Possibly, a scapegoat tree implementation could be altered to store the counts in the nodes, and then similarly support indexed access. Perhaps the caching of the sizes could help the scapegoat operations also; I would have to dive into the details again to check this idea. However, it's a virtue of the original algorithm that the nodes don't have to store any meta-data related to the algorithm. Not even one bit (like in the red-black tree case, for color).
zug_zug 2y ago
Also known as an order-statistic tree. Good for obscure leetcode problems, though I've never needed to implement one in my whole career. [1] https://en.wikipedia.org/wiki/Order_statistic_tree https://en.wikipedia.org/wiki/Order_statistic_tree
- erikrozendaal 2y ago
  Funnily enough this is (was?) used by the Scala collection library's TreeSet/TreeMap, for fast performance of the `take` and `drop` operations. This is a red-black tree though, not a B-Tree. Commit https://github.com/scala/scala/pull/82/commits/b7e671446892c232afdfb5e36ceeab135ece649b https://github.com/scala/scala/pull/82/commits/b7e671446892c... of PR https://github.com/scala/scala/pull/82 https://github.com/scala/scala/pull/82
- throw_pm23 2y ago
  Hard to evaluate your comment without knowing in what field your career is.
- josephg 2y ago
  I’ve done a few implementations of this data structure recently. It’s an essential part of making a high performance CRDT for collaborative text editing. I haven’t found any decent 3rd party order statistic tree online that I can use for CRDTs for 2 reasons: 1. I want my tree to be internally run-length encoded. Ie, each item in my tree represent an adjacent runs of inserted characters in the document. In my tests, this seems to make the data structure about 20x smaller. But it adds complexity - we also need to be able to later split those runs if we discover an insert in the middle of any run. 2. I also need random access. Items have a unique ID, and I need to be able to find any item by looking up its ID. The IDs are just auto incremented integers to make the run length encoding work. You end up with a pretty custom set of data structures, but the result is a system which performs fabulously well in practice. The fastest implementation I know of of this stuff is the Cola crdt library, which is written in 100% safe rust.
  - yencabulator 2y ago
    FYI "run-length encoded" means compressing repetitions. "123 repeats of the character 'x'" would be RLE. You seem to be talking about keeping a tree-of-strings instead of tree-of-characters, to decrease the overhead. https://en.wikipedia.org/wiki/Run-length_encoding https://en.wikipedia.org/wiki/Run-length_encoding
evanrelf 2y ago
Like Zed's `SumTree`! https://zed.dev/blog/zed-decoded-rope-sumtree https://zed.dev/blog/zed-decoded-rope-sumtree
veltas 2y ago
Maybe this is useful for real time memory management? 'arrays' for instance, if dynamically sized, can always cause fragmentation. It feels like you can get relatively efficient traversal and random access in these counted b-trees with fixed size blocks all the way down.

98 points by zerojames 2y ago

This approach is essentially what is called an "augmented data structure". Namely, in this case a B-tree is augmented to store an element count. But there are obviously many other data structures to which this can be applied, and many types of additional values that can be stored. https://www.geeksforgeeks.org/introduction-to-augmented-data-structure/ https://www.geeksforgeeks.org/introduction-to-augmented-data... https://tildesites.bowdoin.edu/~ltoma/teaching/cs231/fall09/Lectures/10-augmentedTrees/augtrees.pdf https://tildesites.bowdoin.edu/~ltoma/teaching/cs231/fall09/... https://www.cs.toronto.edu/~tabrown/csc263/2014W/week4.interval.pdf https://www.cs.toronto.edu/~tabrown/csc263/2014W/week4.inter...

cb321 2y ago

Some here are questioning the motivation of this data structure. It is well motivated at least in the context of time series. We (almost) all learn 2 things at very young ages: 1) the world changes and 2) even one wild point can pollute an average. In time series contexts, we also learn early solutions to 1) a moving data window (flat or fancily weighted over time) and 2) percentiles/quantiles/order statistics are more robust. Combining the two solutions means you want to efficiently delete old/insert new/query quantiles over moving data windows. If you need multiple (e.g. 1%, 25%, median, 75%, 99% is a classic case) and exact quantiles over large data windows (in numbers of points), a counted B-tree is about as good as you can do, and can be many orders of magnitude less work than more naive solutions (which absolutely show up In The Wild - I have personally seen them many times). There is a case that article does not address when you have many-way ties aka many duplicate keys, but that can be handled within the same general framework. If you know something about the dynamic range of your data then you can also get more approximate dynamic quantiles with a histogram with log/exp-spaced bins (like floats) with counters backed by a Fenwick Tree (to make both PDF & CDF updates efficient). You can further boost accuracy with Parzen mid-quantile interpolation. A fully worked example in Nim is at https://github.com/c-blake/adix/blob/master/adix/lghisto.nim https://github.com/c-blake/adix/blob/master/adix/lghisto.nim In the same github repo there is also a Nim implemention of counted B-trees (though it is harder to use).

kragen 2y ago
this is an excellent example of when you'd want to use counted b-trees, but much more generally, they provide a middle ground between arrays and linked lists in arrays, indexing is fast (one instruction), but insertion and deletion is slow in linked lists, indexing is slow, but insertion and deletion are fast (≈10 instructions) (iteration is fast in both, though on modern cpus you have to store multiple items per linked-list node for that to remain true) in counted b-trees, both indexing and insertion/deletion are fast, though not as fast as in arrays or linked lists: logarithmic time instead of constant time, with a larger constant factor

muizelaar 2y ago

Does anyone know of a persistent/on-disk implementation of this kind of data structure?

deleted 2y ago
[deleted]

nayuki 2y ago

The order statistic tree was covered in the CLRS book. In the 4th edition, it is chapter 17 "Augmenting Data Structures", subchapter 1 "Dynamic order statistics". (I know for a fact it was present in the 3rd and 2nd editions too; did not check the 1st.) I used this knowledge to implement a tree-based list data structure, with no set functionality at all: https://www.nayuki.io/page/avl-tree-list https://www.nayuki.io/page/avl-tree-list

cb321 2y ago
By separating "seek" (min/max/key/nth) from "edit" (in-del) and "balance" (AVL, red-black, etc.) operations, you can indeed cover a lot of bases as elaborated here: https://github.com/c-blake/bst https://github.com/c-blake/bst (including also how you handle duplicate keys as well as the perhaps less useful neither-ranked-nor-keyed access, wherein the trees are kind of a double-ended queue with just "edge access").
- turndown 2y ago
  >perhaps less useful neither-ranked-nor-keyed access, wherein the trees are kind of a double-ended queue with just "edge access" For normal btrees this is absolutely true. For b+trees you will see this basically everywhere.

samsquire 2y ago

I've been interested in this data structure for the ability to scan forward efficiently to any depth. I am thinking of a binary protocol that can be navigated extremely efficiently and also be inserted into at any depth.

tidwall 2y ago

A working example in Go. https://github.com/tidwall/btree https://github.com/tidwall/btree

James_K 2y ago

Good examples of this would be the "rope" used in various text editors and Clojure's persistent vector data type.

kragen 2y ago

probably if you like this data structure you will want to read raph levien's extensive treatise on its many variations and applications, specifically with respect to writing text editors, entitled "rope science": https://xi-editor.io/docs/rope_science_00.html https://xi-editor.io/docs/rope_science_00.html

kazinator 2y ago

Scapegoat trees make use of subtree counts. But, according to Rivest's description of the algorithm, they are not stored; the counts are dynamically calculated when needed. Possibly, a scapegoat tree implementation could be altered to store the counts in the nodes, and then similarly support indexed access. Perhaps the caching of the sizes could help the scapegoat operations also; I would have to dive into the details again to check this idea. However, it's a virtue of the original algorithm that the nodes don't have to store any meta-data related to the algorithm. Not even one bit (like in the red-black tree case, for color).

zug_zug 2y ago

Also known as an order-statistic tree. Good for obscure leetcode problems, though I've never needed to implement one in my whole career. [1] https://en.wikipedia.org/wiki/Order_statistic_tree https://en.wikipedia.org/wiki/Order_statistic_tree

erikrozendaal 2y ago
Funnily enough this is (was?) used by the Scala collection library's TreeSet/TreeMap, for fast performance of the `take` and `drop` operations. This is a red-black tree though, not a B-Tree. Commit https://github.com/scala/scala/pull/82/commits/b7e671446892c232afdfb5e36ceeab135ece649b https://github.com/scala/scala/pull/82/commits/b7e671446892c... of PR https://github.com/scala/scala/pull/82 https://github.com/scala/scala/pull/82
throw_pm23 2y ago
Hard to evaluate your comment without knowing in what field your career is.
josephg 2y ago
I’ve done a few implementations of this data structure recently. It’s an essential part of making a high performance CRDT for collaborative text editing. I haven’t found any decent 3rd party order statistic tree online that I can use for CRDTs for 2 reasons: 1. I want my tree to be internally run-length encoded. Ie, each item in my tree represent an adjacent runs of inserted characters in the document. In my tests, this seems to make the data structure about 20x smaller. But it adds complexity - we also need to be able to later split those runs if we discover an insert in the middle of any run. 2. I also need random access. Items have a unique ID, and I need to be able to find any item by looking up its ID. The IDs are just auto incremented integers to make the run length encoding work. You end up with a pretty custom set of data structures, but the result is a system which performs fabulously well in practice. The fastest implementation I know of of this stuff is the Cola crdt library, which is written in 100% safe rust.
- yencabulator 2y ago
  FYI "run-length encoded" means compressing repetitions. "123 repeats of the character 'x'" would be RLE. You seem to be talking about keeping a tree-of-strings instead of tree-of-characters, to decrease the overhead. https://en.wikipedia.org/wiki/Run-length_encoding https://en.wikipedia.org/wiki/Run-length_encoding

evanrelf 2y ago

Like Zed's `SumTree`! https://zed.dev/blog/zed-decoded-rope-sumtree https://zed.dev/blog/zed-decoded-rope-sumtree

veltas 2y ago

Maybe this is useful for real time memory management? 'arrays' for instance, if dynamically sized, can always cause fragmentation. It feels like you can get relatively efficient traversal and random access in these counted b-trees with fixed size blocks all the way down.