// Adam Prout explains one of the key technical features
// that distinguishes SingleStore: its use of skiplist indexes
// over Btrees and similar structures.
// The most popular data structure used for indexing
// in relational databases is the Btree (or its variant,
// the B+tree). Btrees rose to popularity because they
// do fewer disk I/O operations to run a lookup compared
// to other balanced trees.
//
// SingleStore uses a skiplist, not a Btree, as its primary
// index backing data structure for in-memory data.
// Btrees made a lot of sense for databases when the
// data lived most of its life on disk and was only pulled
// into memory and cached as needed to run queries.
//
// On the other hand, Btrees do extra work to reduce
// disk I/O that is needless overhead if your data fits
// into memory. As memory sizes have increased, it is
// feasible today to support indexes that only function
// well for in-memory data, and are freed from the
// constraints of having to index data on disk. A skiplist
// is well suited for this type of indexing.
// A skiplist is an ordered data structure providing
// expected O(Log(n)) lookup, insertion, and deletion
// complexity. It provides this level of efficiency without
// the need for complex tree balancing or page splitting
// like that required by Btrees, redblack trees, or AVL
// trees. As a result, it’s a much simpler and more
// concise data structure to implement.
// Lock-free skiplist implementations have recently
// been developed; see this paper, Lock-Free Linked Lists
// and Skiplists, published in 2004 by Mikhail Fomitchev
// and Eric Ruppert. These implementations provide
// thread safety with better parallelism under a concurrent
// read/write workload than thread-safe balanced trees that
// require locking.
// A skiplist is made up of elements attached to towers.
// Each tower in a skiplist is linked to the next tower
// at the same height, forming a group of linked lists,
// one for each level of the skiplist.
//
// When an element is inserted into the skiplist, its
// tower height is determined randomly via successive
// coin flips (a tower with height n occurs once in 2^n times).
// The element is linked into the linked lists at each level
// of the skiplist, once its height has been determined.
// The towers support binary searching by starting at the
// highest tower and working towards the bottom,
// using the tower links to check when one should move
// forward in the list or down the tower to a lower level.
// There are many reasons why skiplists are best for
// SingleStore, primarily: they’re memory-optimized,
// simple (including the need for many fewer lines of
// code to implement them), much easier to implement
// in a lock-free fashion, fast, and flexible.
AmitKumarDas
commented
3 years ago