Hacker News Reader

It'd be interesting to see it compared to https://doc.rust-lang.org/std/collections/struct.BTreeSet.ht....

Their skiplist description is a little funny — typically a skiplist has one element per leaf node, and you should never need to move items between buckets. Also skiplists have logarithmic layers in the number of elements, so inserting and searching are always bounded by O(log n).

View on HN

I've been using a bucketized version of skiplist for years now, I thought I invented it! Using most recently in https://github.com/infradig/trealla (a Prolog interpreter).

We needed to support arbitrary index access into the sorted set - which is why stdlib btree map doesn't work.

For binary trees, indexing can be done by saving the subtree size of each node and doing a sort of binary search. Not sure if this is fast for B-trees that have more than 2 children nodes, though.

Do you mean OSTs?

https://en.wikipedia.org/wiki/Order_statistic_tree

Oh, that makes sense. I like the solution you arrived at!

Reply on news.ycombinator.com