B+Tree的持久化

大部分都知道B樹的效率高，但是大家知道B樹是怎麼存在硬碟上的嗎？

Btree的實現通常都是基於內存，數據結構大家比較清楚：

struct Node{ int keynum; /* 結點中關鍵字的個數，即結點的大小*/ struct Node *parent; /*指向parent結點*/ int key[m]; /*關鍵字向量*/ struct Node *ptr[m]; /*子樹指針向量*/ };

到底B樹是如何存進硬碟，已達到快速查找的呢？讓我們來一探究竟！

不清楚硬碟讀寫原理的朋友可以先粗略了解一下：深入了解硬碟的讀寫原理和碎片的產生

不清楚Btree的朋友上網隨便搜索了解一下。

先上一張B+Tree的圖：

關於更多b tree索引可以看：http://www.toadworld.com/platforms/oracle/w/wiki/11001.oracle-b-tree-index-from-the-concept-to-internals

硬碟的每一個Block對應B樹的一個Node，每個Block存儲一個node+剩餘的一些空間以便調整結構。

每個Block可以是葉子結點，也可以是分支節點。

假設每個block的大小是10K（具體還要看硬碟）：

1.一個10G的文件（1000個Block）；

2.第一個Block會分配給根節點，餘下的節點會分配給leaf和branch；

3.數據插入、刪除、修改，和普通B+tree操作一樣，只不過是具體化到硬碟。

當我們需要讀數據時候我們可以這樣：

1.讀第1個block(seek(0), read(10k))，查到對應的子節點，假設為定位在第900個block；

2.讀第900個block (seek(900*10k), read(10K)) ，查到對應的葉子節點，假設為定位在第5000個block；

3.讀第1500個block(seek(5000*10k), read(10K))，這時候數據就在這裡了。

那麼問題來了：如何把在內存的b+tree具體化到硬碟呢？

b+tree在內存中使用的是指針，無法具現化到硬碟。難道我們要把指針的地址存進硬碟嗎？這顯然是不可能實現，即使存進去，下次載入的時候該內存塊已經沒有你想要的內容了。

我們只能pointer轉變為具體id,這裡成為結點號。

每個node分配一個id，然後指向下一個node的id，在文件中具體的形式可能是這樣：

[parent_id, key_num, key[], value, child_id]（ps:在各種高級資料庫可能有不同的現實)

將該數據存入每個block中，然後讀幾次磁碟IO就可以獲取到相應的數據。

那麼問題又來了，我們怎麼把文件載入內存 或者說 重構b樹？

我們程序是無法直接訪問設備的，一般通過用戶空間->內核空間->設備的方式訪問硬體。

那麼有沒有別的辦法可以解決這個問題呢？我目前知道一種mmap的方法，可能有其他更高級的方法，知道的可以評論一下。

mmap（一種內存映射文件的方法）:

mmap操作提供了一種機制，讓用戶空間直接訪問設備內存，這種機制，相比較在用戶空間和內核空間互相拷貝數據，效率更高。在要求高性能的應用中比較常用。mmap映射內存必須是頁面大小的整數倍，面向流的設備不能進行mmap，mmap的實現和硬體有關。

mmap在每種程序語言都有不同實現，這裡就不展開說明。

請繼續關注我，下次把golang的版本寫出來，再來說一說。