Skip to main content

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 O(logn){\mathcal {O}}(\log n) search complexity as well as O(logn){\mathcal {O}}(\log n) insertion complexity within an ordered sequence of nn 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.