如何在磁盤上佈置B-Tree數據？

Question

我知道B-Tree是如何在內存中工作的，它很容易實現。然而，什麼是目前完全超越我的，是如何找到數據的佈局，在磁盤上有效地工作，使得：

• 條目在B樹的數量可以indefinitly增長（或至少> 1000GB ）
• 磁盤級複製操作最小化
• 值可以有任意的大小（即沒有固定的模式）

如果有人可以提供深入瞭解布點在磁盤上的B級樹結構，我想非常感謝。特別是最後一點讓我頭痛不已。我也很欣賞指向書籍的指針，但是我所見過的大多數數據庫文獻僅解釋了高級結構（即「這是你如何在內存中執行它」），但跳過了磁盤佈局上的細節。

Answer 1

有關甲骨文公司的指數內部的一些信息：http://www.toadworld.com/platforms/oracle/w/wiki/11001.oracle-b-tree-index-from-the-concept-to-internals

注：

數據庫都不能直接實現基於B樹，但在變異指標稱爲B +樹。其中根據維基百科：

A B +樹可以被看作是一個B-樹中，每個節點僅包含鍵（未鍵 - 值對），以及其中附加電平被添加在底部與鏈接樹葉。

數據庫的工作，一般來說，面向塊的存儲和b +樹更適合於這個b-tree。

塊是固定的大小，並留有一些可用空間，以適應未來價值或密鑰大小的變化。

A嵌段可以是葉（保持實際數據）或分支（保持指針的葉節點）

的玩具模型寫入到磁盤如何可以被實現（對於塊大小10K用於算術簡化）：

1. 10G的一個文件在磁盤上創建（它有塊1000）
2. 第一塊指定爲根和下一個空閒酮作爲葉和葉片的地址的列表被放入根
3. 插入的新數據，當前葉號解填充的值，直到達到閾值被
4. 數據繼續被插入時，下一個自由的被分配爲葉塊和葉節點的列表被許多後更新
5. 插入，當前根節點需要子節點，因此下一個空閒塊被分配爲分支節點，它將從根目錄複製列表，現在根將只維護一箇中間節點列表。
6. 如果要分割節點塊的需要，下一個空閒塊被分配爲分支節點時，加入到根表和葉節點的列表被初始和新的分支節點

當之間分割信息是從一個大的索引讀：可以去以下：

1. 讀出的第一/根塊（尋道（0），讀（10K）），其指向位於在塊900
2. 讀的兒童塊900（尋找（900 * 10k），讀取（10K））哪個p向位於塊5000中的孩子提供子塊
3. 讀取塊5000（搜索（5000 * 10k），讀取（10K）），其指向位於塊190中的葉節點
4. 讀取塊190（搜索（190 * 10k ），讀（10K）），並提取感興趣的值從它

一個非常大的索引可以對多個文件進行分割，然後塊的地址將是東西爲（filename_id，address_relative_to_this_file）

Answer 2

讀它 這無疑將有助於 http://www.geeksforgeeks.org/b-tree-set-1-introduction-2/