luc*_*nce 9 database b-tree skip-lists data-structures
我正在阅读跳过列表和MemSQL,并想知道为什么跳过列表在数据库中没有被更广泛地使用？使用跳过列表是否有任何重大缺陷？
tem*_*def 14
数据库通常非常庞大,必须存储在外部存储器中,例如巨型磁盘驱动器.因此,大多数数据库应用程序的瓶颈是我们必须从磁盘驱动器到主内存进行内存传输的次数.
B树及其变体专门设计用于最小化执行每个操作所需的块读取和写入次数.在数学上,每个B树操作所需的内存传输数是O(log n/log B),其中B是块大小.将其与跳转列表进行比较,跳转列表需要O(log n)内存传输.由于B通常以兆字节为单位测量,因此log B可以在15-25附近,因此B树可以明显更快.即使数据库在主存储器中,存储器层次结构(L1和L2高速缓存等)的影响也是如此明显,以至于B树变体在实践中仍然比许多其他数据结构更快.这篇谷歌博客文章给出了一些背景知识.
虽然B树上的每个操作通常比其他数据结构中的相应操作需要更多的CPU工作,但是它们需要如此少的存储器传输的事实往往使它们在实践中比其他数据结构明显更快.因此,不建议在数据库中使用跳过列表.
B树很好的另一个原因是:它们的效率最差.尽管确实存在跳过列表,但大多数跳过列表实现都是随机的,并为其行为提供预期的保证.在数据库中,这可能是不可接受的,因为数据库上的许多用例需要最坏情况下的有效行为.
希望这可以帮助!
小智 8
虽然游戏已晚，但我很想回复它，因为它是最受好评的答案，而且可能没有传达完整的信息。
跳过列表与平衡树数据结构不同，因为它允许有效地组合多个列表。在数据库术语中，它允许有效地组合基于跳跃列表的索引。Lucene 就是一个很好的例子，它为 Solr/ElasticSeach 等搜索引擎提供支持。https://issues.apache.org/jira/browse/LUCENE-866。
B-Tree 在组合多个索引时存在问题，而无需先验地对整个组合进行索引，这效率不高，因为它需要对历史记录重新建立索引。
因此，每当数据存储必须支持数据跳过列表上的任意查询时，都是一个理想的选择。