Data structures from scratch
Ordered maps and skip lists
Keys kept in sorted order with logarithmic lookup, insertion and deletion, as a balanced tree behind a `std::map` interface or as a skip list of randomised express lanes. Both also answer range and predecessor queries a hash table cannot.
Reading
CMU 15-445 Database Systems CMU Database Group (Andy Pavlo) 1 video