科技

【[譯]從磁碟結構到B+樹】

簡單來說:按照時鐘方向分,disk由很多個sector組成,編號為0-N。按照從外到內分,disk又由多個track組成,編號為0-N。sector和track交叉的地方,叫做block,每個block有自己的address,可以用(trackno,sectorno)表示。每個block的大小是一樣的,具體的大小要看實際情況,在這裡,我們假設一個block的大小是512bytes。

需要十分明確的一點是:無論是讀操作,還是寫操作,都是以block為單位進行的。

在block內部,可以看作是一個數組結構,座標從0到511。每個byte都有一個address,這個稱為offset。所以我們可以把disk上的每一個byte用(trackno,sectorno,offset)的形式表示。

在計算機中,disk的結構可以這麼簡要地表示。

其中有一個讀寫頭,每個時刻,讀寫頭對準了disk上的其中一個block(trackno,sectorno)。通過旋轉,可以改變sectorno,通過伸縮讀寫頭,可以改變trackno。

還有一點,也是需要明確的:只有disk上的資料被載入到RAM(random access memory),才能被程式使用。或者說,才是真正對程式有用的。

如何優化RAM中資料的效率,這門學問叫做資料結構;如何優化disk中資料的效率,這門學問叫做DBMS,也就是大部分資料庫所要研究的內容。

現在有一個employee table,其中有這些欄位,每個欄位的大小如圖所示,一個record的大小總計為128 bytes。

總共有100行資料:

每個block可以存4行資料。存這100條資料,需要25個block。如果現在我們需要查詢其中的一條資料,最多就需要查詢25個block。

我們建一個簡單的索引,有兩個欄位,一個eid,表示employee的id,還有一個欄位pointer,指向資料儲存在disk上的位置。empolyee中的每一行,在index上都有一條記錄。

那麼我們又是怎麼儲存這個索引的呢?這裡我們假設還是全部存在disk上(當然你完全可以選擇直接存在記憶體裡)。那麼這個索引需要佔據多少個block呢?eid大小為10bytes,pointer大小為6bytes,所以一行索引就有16個bytes大小。100條索引就需要佔據100 * 16 / 512 -> 4個block。

那麼現在要查詢employee表中的某一條資料,最多需要查詢多少個block呢?答案是4+1=5個。效率比之前要高了很多。

現在假設有1000條資料,這1000條資料將佔據250個block,上一小節講的索引將佔據40個block。現在用索引查詢一次,最多需要41次block access。現在這個索引已經不能滿足我們對效能的追求了,那麼能不能對索引建一個索引呢?也就是二級索引?

對於二級索引,不需要記錄每條employee在disk的位置,只需要記錄一級索引所有block的位置就行了。 所以,二級索引需要40條記錄,也就是需要佔據2個block的空間。這種二級索引可以叫做稀疏索引,他不會包含所有資料行所在的位置。

現在藉助二級索引,查詢效率為:2 + 1 + 1 = 4次block access。

隨著資料量不斷增加,還可以對二級索引建立三級索引,對三級索引建立四級索引……

同時,我們還希望做到一點:多級索引可以隨著資料量的大小變化而自動建立和刪除。 這就引出了主角:B樹和B+樹。

二叉搜尋樹:每個節點有一個值,有兩個子節點。

由二叉搜尋樹擴充套件,讓每個節點最多可以存m-1個索引值,每個節點可以有m個子節點,就是m-way搜尋樹。

上圖所示的就是3-way搜尋樹。

下面的這個4-way搜尋樹,每個節點最多存了3個索引值,有4個指向子節點的pointer,同時還有指向資料項所在的位置的指標Rp。

我們可以用這個m-way搜尋樹作為資料庫的索引,但是,m-way搜尋樹存在一些問題:

比如現在有三個資料:10,20,30,要用一個10-way搜尋樹來構建。很有可能,最終會構建出一個這樣的樹:

這是最糟糕的一種情況,最終。我們需要先把每個節點填滿,然後才能建立下一個子節點。而m-way搜尋樹本身,並沒有這種強制,你可以隨意插入。

B樹,實際上可以看作是m-way搜尋樹 + 規則(如何構建這棵樹的規則)。

規則:

值:10,20,40,50。要構建一個4-way搜尋樹。4-way搜尋樹,意味著一個節點最多可以有3個值。

這實際上,也就構建了一個二級索引。上面的是第二層索引,下面的是第一層索引。每一層構成了一級索引。

繼續插入60和70:

接著插入80,右下的那個節點已經沒有空位置了,所以需要新建一個節點,然後把70那個值提升到上一層。

插入30:

插入35:

等等等等:

每個值旁邊,都有一個指向資料儲存位置的指標。

在B+樹中,不是每個值旁邊都有一個指向資料儲存位置的指標,只有葉子節點才有。非葉子節點的值,在葉子節點上有他的副本。如圖所示:

這就成為了一個密集索引。

Reference:科技日報

看更多!請加入我們的粉絲團

轉載請附文章網址

不可錯過的話題