2 ms·
I think this data structure is usually called a Counted B-tree https://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html https://www.chiark.greenend.o
by uyt 5y ago
I think this data structure is usually called a Counted B-tree https://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html https://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtr... instead of range tree
- cryptonector 5y agoXi has/had a rope library that allowed one to apply many monoids at each internal node. So one could search for a position in the document as TFA is doing, but also count bytes, Unicode codepoints, Unicode characters/glyphs/widths, etc. with just one tree. What's common to xi's approach and TFA's is monoids. Monoids are at the heart of CRDT.