R樹

什么是B樹？

本?提到的「B-樹」，就是「B樹」，都是B-tree的翻譯，??不是減號-，是連接符-。因為有?把B-tree翻成「B-樹」，讓?以為「B樹」和「B-

樹」是兩種樹，實際上兩者就是同?種樹。

Mysql數據庫??的索引是基于什么數據結構了呢？

主要是基于Hash表或者B+樹。

B+樹的具體實現細節？B-樹和B+樹有什么區別呢？聯合索引在B+樹中如何存儲呢？

要知道這些，我們需要先了解什么是B-樹。數據庫索引之所以要使?樹結構存儲，是因為樹的查詢效率?，?且可以保持有序。為什么索引不使??

叉查找來樹來實現呢？（///?叉查找樹查詢的時間復雜讀是0（logN），性能已經?夠?了啊，難道B樹可以?它更快？）其實從算法邏輯上講，?叉

查找樹的查找速度和?較次數都是最?的，但是為我們不得不考慮?個現實的問題：磁盤IO。

數據庫索引是存儲在磁盤上的，當數據量?較打的時候，索引的??可能有?個G甚?更多。當我們利?索引查詢的時候，能把整個索引全部加載到

內存嗎？不可能，能做的只有逐?的加載每?個磁盤頁對應著索引樹的節點。

如果我們利??叉查找樹作為索引結構，情形是什么呢？假設樹的?度是4，查找的值是10，流程如下：

由上可以看出，磁盤IO的次數是由索引樹?度決定，所以為了減少磁盤IO次數，我們需要減少樹的?度，這就是B-樹的特征之?。

B樹的定義：

兩種定義：?階定義的B樹&?階定義的B樹

?階定義的B樹：

B樹?叫平衡多路查找樹。?棵m階的B樹(注：切勿簡單的認為?棵m階的B樹是m叉樹，雖然存在四叉樹，?叉樹，KD樹，及vp/R樹/R*

樹/R+樹/X樹/M樹/線段樹/希爾伯特R樹/優先R樹等空間劃分樹，但與B樹完全不等同)的特性如下：

1.樹中每個結點最多含有m個孩?（m>=2）；

2.除根結點和葉?結點外，其它每個結點?少有[ceil(m/2)]個孩?（其中ceil(x)是?個取上限的函數）；

3.若根結點不是葉?結點，則?少有2個孩?（特殊情況：沒有孩?的根結點，即根結點為葉?結點，整棵樹只有?個根節點）；

4.所有葉?結點都出現在同?層，葉?結點不包含任何關鍵字信息(其實，關鍵是把什么當做葉?結點，因為如紅?樹中，每?個NULL

指針即當做葉?結點，只是沒畫出來?已）。

5.每個?終端結點中包含有n個關鍵字信息：(n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：

a)Ki(i=1...n)為關鍵字，且關鍵字按順序升序排序K(i-1)

b)Pi為指向?樹根的接點，且指針P(i-1)指向?樹種所有結點的關鍵字均?于Ki，但都?于K(i-1)。

c)關鍵字的個數n必須滿?：[ceil(m/2)-1]<=n<=m-1。如下圖所?：

?度定義的B樹：

針對上?的5點，再闡述下：B樹中每?個結點能包含的關鍵字（如之前上?的DH和QTX）數有?個上界和下界。這個下界可以??個

稱作B樹的最?度數（算法導論中?版上譯作度數，最?度數即內節點中節點最?孩?數?）m（m>=2）表?。

每個?根的內結點?多有m個??，每個?根的結點必須?少含有m-1個關鍵字，如果樹是?空的，則根結點?少包含?個關鍵字；

每個結點可包含?多2m-1個關鍵字。所以?個內結點?多可有2m個??。如果?個結點恰好有2m-1個關鍵字，我們就說這個結點是滿的

（?稍后介紹的B*樹作為B樹的?種常?變形，B*樹中要求每個內結點?少為2/3滿，?不是像這?的B樹所要求的?少半滿）；

當關鍵字數m=2（t=2的意思是，mmin=2，m可以>=2）時的B樹是最簡單的（有很多?會因此誤認為B樹就是?叉查找樹，但?叉查找樹就

是?叉查找樹，B樹就是B樹，B樹是?棵含有m（m>=2）個關鍵字的平衡多路查找樹），此時，每個內結點可能因此?含有2個、3個或4個

??，亦即?棵2-3-4樹，然?在實際中，通常采??得多的t值。

上圖是?顆階數為4的B樹。在實際應?中的B樹的階數m都?常?（通常?于100），所以即使存儲?量的數據，B樹的?度仍然?較?。每

個結點中存儲了關鍵字（key）和關鍵字對應的數據（data），以及孩?結點的指針。我們將?個key和其對應的data稱為?個記錄。

B-樹的查詢：

演?如下：假設查詢5

插?：

B-樹的插?過程?較復雜，我們只舉?個最?典的例?，插?4

刪除：11