Skip list - Wikipedia

In computer science, a skip list (or skiplist) is a probabilistic data structure that allows average complexity for search as well as average complexity for insertion within an ordered sequence of 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. Fast search

[perezvon]

skip list

[tagomoris]

Indexable skiplist

[ita-wasa]

Indexable skiplist As described above, a skiplist is capable of fast Θ(log n) insertion and removal of values from a sorted sequence, but it has only slow Θ(n) lookups of values at a given position in the sequence (i.e. return the 500th value); however, with a minor modification the speed of rando

[odz]

Skip List。後で読む

[hassylin]

エンジンじゃないんだけど、適当なタグが無いので。