Re:Using Rust to Scale Elixir for 11M Concurrent Users (2019)
by infradig on Wednesday November 11, 2020 @02:55AM
(#25056373)
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).
Re:Using Rust to Scale Elixir for 11M Concurrent Users (2019)
by jhgg on Tuesday November 10, 2020 @09:38PM
(#25054954)
We needed to support arbitrary index access into the sorted set - which is why stdlib btree map doesn't work.
Re:Using Rust to Scale Elixir for 11M Concurrent Users (2019)
by c0deb0t on Tuesday November 10, 2020 @09:54PM
(#25055040)
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.
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).