[Skip Lists](https://courses.cs.umbc.edu/undergraduate/341/fall01/Lectures/SkipLists/skip_lists/skip_lists.html) 書籍[[Database Internals]] 7.3.3節にて次のように記載されている。 > ソート済みのデータをメモリ内に保持する手段としては、多くの異なったデータ構造が存在し ます。その中でも、その単純さのために最近人気なのは、スキップリスト [PUGH90b] と呼ばれる データ構造です。 > Apache [[Cassandra]]では、スキップリストがセカンダリインデックスのmemtableの実装(https: //databass.dev/links/81)に使用されています。また、WiredTiger では、スキップリストが一部 のインメモリ操作で使用されています。 平均時間計算量はinsert/update/delete $\mathcal{O}(n)$