16

我正在阅读有关跳过列表和 MemSQL 的内容，想知道为什么跳过列表在数据库中没有得到更广泛的使用？使用跳过列表有什么主要缺点吗？

4

2 回答 2

24

数据库通常非常庞大，以至于它们必须存储在外部存储器中，例如巨大的磁盘驱动器。因此，大多数数据库应用程序的瓶颈是我们必须将内存从磁盘驱动器传输到主内存的次数。

B 树及其变体专门设计用于最小化执行每个操作所需的块读取和写入次数。在数学上，每个 B-tree 操作所需的内存传输次数为 O(log n / log B)，其中 B 是块大小。将此与跳过列表进行比较，后者需要 O(log n) 的内存传输以符合预期。由于 B 通常以兆字节为单位，因此 log B 可以在 15 - 25 附近，因此 B-tree 可以明显更快。即使数据库位于主内存中，内存层次结构（L1 和 L2 缓存等）的影响也非常明显，以至于 B-tree 变体在实践中仍然比许多其他数据结构更快。这篇 Google 博客文章提供了一些相关背景信息。

尽管 B 树上的每个操作通常比其他数据结构中的相应操作需要更多的 CPU 工作，但它们需要如此少的内存传输这一事实往往使它们在实践中比其他数据结构快得多。因此，不建议在数据库中使用跳过列表。

B-trees 好的还有另一个原因：它们在最坏情况下是有效的。尽管确实存在确定性跳过列表，但大多数跳过列表实现都是随机的，并对其行为提供预期的保证。在数据库中，这可能是不可接受的，因为数据库上的许多用例都需要最坏情况下的高效行为。

希望这可以帮助！

于 2014-05-22T18:00:34.713 回答
4

虽然它在游戏中很晚，但我觉得作为它的最高评价答案回复的冲动，也许没有传达完整的信息。

跳过列表与平衡树数据结构不同，因为它允许有效地组合多个列表。在数据库方面，它允许有效地组合基于跳过列表的索引。一个很好的例子是 Lucene，它为 Solr/ElasticSeach 等搜索引擎提供支持。https://issues.apache.org/jira/browse/LUCENE-866。

B-Tree 在组合多个索引时存在问题，而不是先验地索引整体组合，这效率不高，因为它需要重新索引历史记录。

因此，每当数据存储必须支持对数据跳过列表的任意查询时，都是理想的选择。

于 2018-01-22T08:40:12.447 回答