Ordered Linked List vs B-Tree

如果您有一棵b +樹作爲索引，那麼這似乎與有序鏈接列表非常相似。但是，有序的鏈表似乎有一些優點，比如不必在樹結構中導航，也不必在節點滿時重建節點，而且在樹不匹配時不必重建樹。Ordered Linked List vs B-Tree

誰能回答什麼是使用B樹而不是有序鏈表的原因是什麼？

2011-12-05 Adam Davies

經過一番研究和論文閱讀後，我找到了答案。

爲了應對大量的數據，比如數百萬條記錄，索引必須被組織成集羣。羣集是磁盤上連續的一組扇區，可以快速讀入內存。這些通常長約4096個字節。

如果我們組織我們的索引，使每個簇包含指向數據的磁盤（數據集羣）上的索引的有序列表，我們可以有一個有序列表索引。

所以，如果我們正在尋找一個特定的記錄，我們怎麼知道哪個集羣是嗎？我們執行二進制搜索來查找正在討論的集羣[O（log n）]。

但是，要做到我們需要知道在每個數據羣值的範圍二進制搜索，所以我們需要元數據，上面寫着分鐘，每個集羣的最大值並在該集羣。這很棒。除非每個數據集羣包含100個索引，並且我們的元數據集羣還包含100個索引，那麼我們只能訪問100個數據集羣。這相當於10 000條記錄（100 X 100）。

那麼這還不夠。讓我們添加另一個元數據集羣，現在我們可以訪問1 000 000條記錄。那麼，我們如何知道爲了找到我們的目標數據集羣，我們需要查詢三個元數據集羣中的哪一個。我們可以一個接一個地搜索它們，但這並不能縮放，平均O（n/2）。因此，我添加了另一個元元數據羣集來指示我應該查詢哪三個元數據羣集來查找目標數據羣集。現在我有一棵樹！

所以這就是數據庫使用樹的原因。這不是速度，而是索引的大小以及需要索引引用其他索引的需求。上面描述的是B +樹 - 子節點包含對其他子節點或葉節點的引用，並且葉節點包含對磁盤上數據的引用。

唷！

來源

2011-12-06 18:53:53

那麼，至少我們有一個答案，謝謝！ – bpgergo

中有許多特點的差異，但我要強調的搜索時間。

而搜索是爲O（log n）的時間在B +樹是O（n）的時間在鏈表，即使是排序。

來源：http://en.wikipedia.org/wiki/Linked_list，http://en.wikipedia.org/wiki/B%2B_tree

來源

2011-12-05 11:24:17 bpgergo

事實並非如此。如果列表是有序的，並且您知道元素的數量（使用一些元數據很容易），那麼您可以使用二進制搜索，即O（log n）http：//en.wikipedia。另外，樹中的每個節點都需要知道最小值和最大值，因此一旦找到了目標節點，仍然必須在該節點上執行二進制搜索。因此，有序列表應該更快（沒有節點導航加上重新構建等）。 –

我也想過二進制搜索。我嚴重懷疑鏈表是否可行（即使是有序的）。我總結說，不知何故它可以被實現，但是實現將依賴於列表本身如何在內存中實現和表示。你能告訴我你將如何獲得中間元素而無需遍歷半個元素？ – bpgergo

middleElement = list [listLength-1/2]; // -1取決於你所謂的中間元素，其中listLength甚至是有關更完整的算法，請參閱http://www.algolist.net/Algorithms/Binary_search。但是，實現並不重要。重要的問題是它能否比B-Tree更快地考慮到所有其他需要進行的維護問題（重新平衡等）。或者我錯過了什麼？ –

在二進制搜索樹，O（log n）的搜索時間是平均情況下。在最壞的情況下，當樹完全不平衡並且類似於鏈表時，搜索需要O（n）時間。

來源

2011-12-05 22:23:02 bpgergo

排序列表中的項目可以通過二進制搜索找到。所以它是O（log n）。對不起，隊友，但這是二進制搜索的定義。例如http://docs.oracle.com/javase/6/docs/api/java/util/Collections.html#binarySearch(java.util.List,%20T）。要明確的是，RandomAccess列表是一個列表，其元素可以通過索引的任意隨機值進行訪問（只要值在範圍內） –

從您鏈接的文檔中：二進制搜索「以log（n）如果指定的列表沒有實現RandomAccess接口並且很大，這個方法將執行一個基於迭代器的二進制搜索來執行O（n）鏈接遍歷和O（log n）元素比較「。想想看：Java [LinkedList]（http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html）**不會**實現[RandomAccess]（http：// docs.oracle.com/javase/6/docs/api/java/util/RandomAccess.html）接口。 – bpgergo

不是在java中，但沒有理由爲什麼它不能作出 –

Ordered Linked List vs B-Tree

回答

相關問題