T-trees：爲什麼它們不用於磁盤索引？

最近我一直在研究B +樹和T-樹。似乎有一種趨勢，B +樹用於磁盤索引，T樹用於內存。T-trees：爲什麼它們不用於磁盤索引？

我相信這是由於磁盤I/O，但我找不到任何證實該概念的東西。我在這個假設中糾正了嗎？另外，如果T樹的磁盤訪問可能被限制爲通過緩存記錄B，那麼它們在logB N處的性能是否會超過B +樹？

2013-02-18 max

如果通過高速緩存限制日誌B，則基本上說，讀取的節點數量與索引大小無關。出於參數的原因，修復B = 2，這樣你的索引必須足夠大，以至於只有最後一個節點被讀取。我認爲這意味着所有的內部節點都必須適合緩存。回到任意大小的索引，你有一個任意大小的緩存。 – DrC 2013-02-18 23:25:02

@DrC，你完全正確。假設只緩存每個節點的最小/最大值和子指針，這意味着B可以更大，而樹中每個節點的內存成本保持不變。假設你需要64個字節來緩存每個節點的最小/最大/左/右和B = 128。基於N = 1024和B = 128的log（N/B），高度應該是log2（1024/128）或3，並且有7個總節點（2^h-1）。所以每個節點有7個節點和64個字節，只有448個字節。因此，mem的成本隨着節點數不爲N而增加。這導致了你的結論，即在日誌B只有最後一個節點從磁盤讀取。 – max 2013-02-19 03:30:45

T樹本質上是一棵二叉樹。因此，樹的深度類似於T樹的log2（N/B）與B +樹的logB（N）（N =＃個數據項，B =每個節點中存儲的密鑰的數量= B的分支因子+樹）。這些都是近似的，因爲每棵樹中都沒有固定數量的項目。無論如何，對於大N來說，B +樹會在該指標上輕鬆獲勝。在統一內存訪問的假設下，這個數字並不重要，但它對二級存儲非常重要，它大約是二級存儲訪問的數量。它也對具有分層存儲器的現代機器（在Vax 11/750上測試的原始T-Tree紙張）很重要。

我在上面做了一些假設，包括如何更新各個環境的兩種結構。我相信他們是對稱和公平的。我主要假設數據和密鑰通過引用存儲在內存中，並通過二級存儲進行復制。如果不以這種方式調整結構，對於具有統一訪問成本作爲其設計核心的T樹而言將是災難性的，因爲每個關鍵比較都需要外部訪問。對於非固定尺寸的數據，在這兩種情況下都需要其他一些包裝調整（並在現實世界中使用）。

來源

2013-02-18 18:32:00 DrC

T-trees：爲什麼它們不用於磁盤索引？

回答

相關問題