# 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.