List Type about list HOT 2 CLOSED

Good question. I should probably document that somewhere.

It's an implementation of relaxed radix balanced trees (RRB-trees).

By far the easiest to understand introduction to the data structure is this series of blog posts. The blog posts describes a simpler version of the data structure. I'm sure if it has a specific name but most often it's simply called "persistent vector".

List implements an extension to the persistent vector called relaxed radix balanced search trees. They were invented in this paper (the paper isn't that easy to understand though). I've found that this thesis is the best explanation of RRB-trees. This thesis also has some additional implementation techniques. I've also added a few ideas on my own in the implementation to speed things up further 😄

from list.

Wow these documents are very interesting.
Thanks

from list.