Articles SortedSet[0] is basically a pseudo-BTree with fixed depth = 2 and fixed max_size of leafs. This gives O(log n) search and O(sqrt n) inserts [1]. It wo

Articles SortedSet[0] is basically a pseudo-BTree with fixed depth = 2 and fixed max_size of leafs. This gives O(log n) search and O(sqrt n) inserts [1]. It would mean that insertion at beginning is worst case scenario (split + need to move all buckets), but timing of insert is actually dominated by adding size of the buckets to calculate final index. Spending a little bit of time on research, finding https://en.wikipedia.org/wiki/Order_statistic_tree https://en.wikipedia.org/wiki/Order_statistic_tree and just using G++ implementation would probably yield better result and less code to support. G++ has __gnu_pbds which add O(log n) "find_by_order" and "order_of_key" to trees, e.g. [2]. [0] https://github.com/discord/sorted_set_nif/blob/master/native/sorted_set_nif https://github.com/discord/sorted_set_nif/blob/master/native... [1] Technically O(n/max_size + max_size) but we can assume that max_size is selected to be ~sqrt n [2] https://www.ideone.com/8mzxGR https://www.ideone.com/8mzxGR