爲什麼跳過列表不優先於數據庫的B +樹？

Question

我正在閱讀有關跳過列表和MemSQL，並想知道爲什麼跳過列表不在數據庫中更廣泛使用？使用跳過列表有什麼主要缺點嗎？

Answer 1

數據庫通常如此巨大，它們必須被存儲在外部存儲器中，如一個巨大的磁盤驅動器。因此，大多數數據庫應用程序的瓶頸是我們必須執行從磁盤驅動器到主內存的內存傳輸的次數。

B樹和其變體是特別設計以最小化數目的塊的讀取和寫入必要執行他們的每一個操作。在數學上，每個B樹操作所需的內存傳輸數量爲O（log n/log B），其中B是塊大小。將它與一個跳過列表進行比較，該列表需要根據期望進行O（log n）內存傳輸。由於B通常以兆字節爲單位進行度量，所以log B可以在15-25的範圍內，因此B樹可以快得多。即使數據庫位於主內存中，內存層次結構（L1和L2緩存等）的影響也可能非常明顯，以至於B-tree變體在實踐中的速度比其他許多數據結構還要快。 This Google blog post給出了一些背景。

雖然在B樹的每個操作通常需要比其他數據結構相應的操作更多的CPU的工作，他們需要這麼少的內存傳輸的事實，往往使他們更快顯著在實踐中比其他數據結構。因此，建議在數據庫中使用跳過列表。

還有一個原因B樹很好：它們是最壞情況下的效率。儘管確定性跳過列表確實存在，但大多數跳過列表實現都是隨機的，併爲其行爲提供預期的保證。在數據庫中，這可能是不可接受的，因爲數據庫上的許多用例需要最差情況下的有效行爲。

希望這會有所幫助！

Answer 2

雖然它在遊戲後期，但我覺得衝動作爲其最精彩的答案回答，也許不傳達完整的信息。因爲它允許有效地結合幾個名單

跳過列出了從平衡樹的數據結構不同。 以數據庫爲基礎，它允許基於跳過列表的索引進行高效組合。 一個很好的例子是Lucene，它爲Solr/ElasticSeach等搜索引擎提供動力。 https://issues.apache.org/jira/browse/LUCENE-866。

B-樹具有在沒有索引的整體組合的先驗，因爲它需要的歷史記錄重新索引，其效率不高的多個索引組合的問題。

因此，無論何時數據存儲必須支持對數據的任意查詢，跳過列表都是理想的選擇。