Data Structures and Algorithms

Log Structured Merge Trees (LSM)​

A data structure with performance characteristics that make it attractive for providing indexed access to files with high insert volume, such as transactional log data

Skip Lists​

A probabilistic data structure that allows ${\mathcal {O}}(\log n)$ search complexity as well as ${\mathcal {O}}(\log n)$ insertion complexity within an ordered sequence of $n$ elements. Thus it can get the best features of a sorted array (for searching) while maintaining a linked list-like structure that allows insertion, which is not possible with a static array.

Bloom Filters​

A space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set.

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