前面的文章我們已經討論了B樹的基本結構和操作，現在我們來看看數據庫系統中B樹是怎樣被存儲到磁盤文件的。磁盤的訪問和內存的訪問方式是完全不同的，操作系統的虛擬內存機制使得應用程序可以透明的訪問內存；而訪問磁盤時需要藉助系統調用並指定訪問文件的位置，然後還要將文件的內容讀取解析到內存中。
當在設計高效的磁盤數據結構時必須考慮到以上這一區別。下面我們將討論如何設計易於創建、修改和解析的文件格式，討論設計高效磁盤數據結構的通用原則和實踐，這些原則不僅僅只適用於B樹。
事實上有很多可行的方式可以實現B樹的磁盤存儲，這裡我們討論幾個常用的實現方式。每個具體實現的細節可能略有不同，但一般原則是相同的。在真正實現B樹磁盤存儲時，僅僅理解B樹的基本機制(比如節點拆分和合並)是不夠的，許多其它因素也必須一併考慮才能達到最終目的。
在磁盤數據結構中，指針的含義和內存中的含義有很大的不同。事實上可以把磁盤B樹看成是一種文件頁面管理機制：它組織文件頁面並能快速的定位頁面，因此文件的頁面和指針都必須正確的設置和保存到適當的位置。
頁面結構
數據庫系統在數據文件和索引文件中存儲數據記錄，這些文件被劃分為大小固定的稱為頁的單元。頁的大小是文件系統塊的大小的倍數，通常在4到16Kb之間。
B樹中節點分為兩類，包含鍵和數據記錄對的葉子節點，以及包含鍵和指向其它節點指針的非葉子節點。每一個節點由一個或多個頁構成，所以B樹中節點和頁可以認為是等同的。
在最早關於B樹的論文中描述了一種存儲固定大小數據記錄的簡單頁數據組織方式。如圖3-4， 每一頁包含多個由三個成員組成的結構：k存儲鍵，v存儲鍵關聯的值，p指向子頁面。
圖3-4
這種方法很容易實現，但是有一些顯著的缺陷：
- 添加鍵值時為了保持有序需要移動其右邊的元素；
- 僅僅適用於固定大小的數據記錄，無法保存可變大小的數據記錄；
分槽頁結構（Slotted Pages）
當存儲可變大小記錄時我們面臨的主要問題是空閒空間的管理：即刪除數據記錄後釋放空間的回收管理。假如一條待插入數據記錄的大小為N，而此前刪除數據記錄的大小為M，除非恰好M等於N，否則就會有M-N的空間不能被利用；同樣的，如果此前刪除數據記錄空間的大小為K，K小於待插入記錄的大小N，那麼刪除釋放的空間也無法直接利用，必須為待插入記錄分配新的空間。
因此，我們需要一種結構，它能夠：
- 能存儲可變大小的記錄，同時額外存儲開銷最小；
- 能回收被刪除記錄佔用的空間；
- 引用記錄時不需要考慮記錄在頁中的具體位置；
分槽頁結構恰巧具有上面這些些特徵，這種頁數據組織方式在許多數據庫中都被使用了，例如PostgreSQL。每個頁面分割為許多槽（Slot或Cell），同時頁面中指針指向這個槽。 指針和槽分佈在頁面的兩個不同的區域中。我們只需要調整指針位置來保證槽中的數據有序即可，刪除記錄時我們也只需要清空或移除指向槽的指針即可。
分槽頁中還包含一個固定大小的頭，一些關於頁和槽的信息被保存在頭中。圖3-5是一個分槽頁的結構示意圖，每一個頁面維護了一個頁頭區域，槽和指向槽的指針。
圖3-5
現在讓我們看看這個是怎麼解決我們的問題：
- 最小的開銷: 分槽頁中的惟一額外開銷是一個指針數組，它保存了記錄在頁面中偏移的準確位置；
- 空間回收: 通過頁面碎片整理並重寫頁面就可以回收空間；
- 動態佈局: 在頁面外部就需要引用槽ID，不需要設計頁面內的具體位置；
槽的結構
這裡我區分鍵槽和鍵值對槽。鍵槽保存一個分割鍵和一個指向子節點頁面的指針；鍵值對槽保存鍵和與之關聯的數據記錄。
我們假設在同一頁上所有的槽的類型是相同的，同一頁面要麼是存儲固定類型的數據記錄要麼就是存儲可變類型的數據記錄。這樣我每一頁上只需要存儲一份描述也信息的元數據，不需要在每一個槽內都維護一份。
對於鍵槽，我們需要保持如下這些信息：
- 槽類型
- 鍵的大小
- 該槽指向的子頁面ID
- 鍵
我們把固定大小的字段放在一起，然後緊跟著的是key_size個比特的鍵。不是要求必須這樣的，但是可以簡化偏移量的計算，因為所有固定大小的字段都可以通過使用靜態的、預先計算好的偏移量來訪問。我們只需要為可變大小的數據計算偏移量。
鍵值對槽（key-value cells）保存數據記錄，具有如下字段：
- 槽類型
- 鍵的大小
- 數據記錄的大小
- 鍵
- 數據記錄
因為頁是固定大小，所以我們只需要保存頁面ID就可以了。在需要時可使直接計算出在文件中的偏移。槽的偏移是相對於頁的偏移的。通過這種方式，我們可以用一個更小的整數就可以保存偏移。
使用槽構成分槽頁
槽（Cell）被保存到頁的右邊，由右邊往左邊擴展；槽的偏移（指針）保存在頁的左邊的偏移數組中，由左往右擴展。如圖3-6。
圖3-6
右邊槽中的鍵不需要按照順序保存，只要左邊槽的偏移指針是按鍵有序保存的即可。這樣插入槽到頁面時開銷最小，因為在插入，更新或刪除時槽都不需要移動。
以一個保存名字的頁面為例：插入兩個名字（先插入Tom，然後插入Leslie）。 Tom所在的槽首先被添加到最右邊，指向該槽的偏移被保存到偏移數組的第一個元素；接下來插入Lesliebe，按字母序Lesliebe在Tom之前，指向Tom的偏移從偏移數組的第一個元素移動到第二個元素，Lesliebe的偏移保存到第一個元素。這樣從偏移數組低位置到高位置依次訪問，名字依然是有序的，可以允許二分查找。
圖3-7
現在再添加一個名子Ron，Ron所在槽被添加到最右邊空閒的位置。但是偏移數組需要保證三個名字是按知名有序的：Leslie, Ron, Tom。為了，我們需要調整偏移數組中各個槽偏移的保存位置，即插入點後面的偏移往右邊移動，空出一個新的位置保存Ron槽的偏移。最終結果如圖3-8。
圖3-8
管理可變大小數據
從頁面（節點）中刪除條目時並不需要刪除實際的條目並移動其它條目到釋放的空間。可以僅僅是將條目標記為已刪除，並報該條目釋放的空間數量和空間位置添加到可用空間列表中。可用空間列表中存儲未被使用存儲空間的偏移量及其大小。在插入新條目時，檢查可用空間列表中是否有適合它的段。如圖3-9中，空閒空間列表保存了所有可用空間的偏移。
圖3-9
在SQLite中，未被使用的空間被稱為空閒塊（free blocks），頁頭中保存了第一個空閒塊的偏移（指針）。另外，頁頭中也保存了頁面所有空閒塊的大小之和，在插入一個新元素可以空閒空間的大小快速的判斷是否可以通過碎片整理獲得足夠的存儲空間。
在為數據選擇空閒塊時，可以根據以下策略進行：
- 首次滿足（Fist Fit）: 第一個大小可以存儲槽的的空閒塊。這種策略可能導致剩下的空間過小，無法存儲任何其它槽而導致空間被浪費；
- 最適合(Best Fit)： 遍歷所以的空閒塊，找到一個大小最匹配的塊，即插入後剩餘空間最小的空閒塊。
如果找不到足夠的連續字節來容納單元，但是有足夠的碎片字節可用，那可以對頁面進行碎片整理，生成足夠大小連續的空間來容納新單元。如果即使在碎片整理之後也沒有足夠的空閒空間，那必須要創建一個溢出頁面（我們後面會繼續討論）。
閱讀更多 壹瓜壹果 的文章
