轉載自:伯樂專欄作者/玻璃貓,微信公衆号 - 夢見 漫畫:什麼是b+樹
這一次我們來介紹 B+ 樹。
一個m階的B樹具有如下幾個特征:
1.根結點至少有兩個子女。
2.每個中間節點都包含k-1個元素和k個孩子,其中 m/2 <= k <= m
3.每一個葉子節點都包含k-1個元素,其中 m/2 <= k <= m
4.所有的葉子結點都位于同一層。
5.每個節點中的元素從小到大排列,節點當中k-1個元素正好是k個孩子包含的元素的值域分劃。
一個m階的B+樹具有如下幾個特征:
1.有k個子樹的中間節點包含有k個元素(B樹中是k-1個元素),每個元素不儲存資料,隻用來索引,所有資料都儲存在葉子節點。
2.所有的葉子結點中包含了全部元素的資訊,及指向含這些元素記錄的指針,且葉子結點本身依關鍵字的大小自小而大順序連結。
3.所有的中間節點元素都同時存在于子節點,在子節點元素中是最大(或最小)元素。
B-樹中的衛星資料(Satellite Information):
B+樹中的衛星資料(Satellite Information):
需要補充的是,在資料庫的聚集索引(Clustered Index)中,葉子節點直接包含衛星資料。在非聚集索引(NonClustered Index)中,葉子節點帶有指向衛星資料的指針。
第一次磁盤IO:
第二次磁盤IO:
第三次磁盤IO:
B-樹的範圍查找過程
自頂向下,查找到範圍的下限(3):
中序周遊到元素6:
中序周遊到元素8:
中序周遊到元素9:
中序周遊到元素11,周遊結束:
B+樹的範圍查找過程
自頂向下,查找到範圍的下限(3):
通過連結清單指針,周遊到元素6, 8:
通過連結清單指針,周遊到元素9, 11,周遊結束:
B+樹的特征:
1.有k個子樹的中間節點包含有k個元素(B樹中是k-1個元素),每個元素不儲存資料,隻用來索引,所有資料都儲存在葉子節點。
2.所有的葉子結點中包含了全部元素的資訊,及指向含這些元素記錄的指針,且葉子結點本身依關鍵字的大小自小而大順序連結。
3.所有的中間節點元素都同時存在于子節點,在子節點元素中是最大(或最小)元素。
B+樹的優勢:
1.單一節點存儲更多的元素,使得查詢的IO次數更少。
2.所有查詢都要查找到葉子節點,查詢性能穩定。
3.所有葉子節點形成有序連結清單,便于範圍查詢。
轉載自:伯樂專欄作者/玻璃貓,微信公衆号 - 夢見 漫畫:什麼是b+樹
這一次我們來介紹 B+ 樹。
一個m階的B樹具有如下幾個特征:
1.根結點至少有兩個子女。
2.每個中間節點都包含k-1個元素和k個孩子,其中 m/2 <= k <= m
3.每一個葉子節點都包含k-1個元素,其中 m/2 <= k <= m
4.所有的葉子結點都位于同一層。
5.每個節點中的元素從小到大排列,節點當中k-1個元素正好是k個孩子包含的元素的值域分劃。
一個m階的B+樹具有如下幾個特征:
1.有k個子樹的中間節點包含有k個元素(B樹中是k-1個元素),每個元素不儲存資料,隻用來索引,所有資料都儲存在葉子節點。
2.所有的葉子結點中包含了全部元素的資訊,及指向含這些元素記錄的指針,且葉子結點本身依關鍵字的大小自小而大順序連結。
3.所有的中間節點元素都同時存在于子節點,在子節點元素中是最大(或最小)元素。
B-樹中的衛星資料(Satellite Information):
B+樹中的衛星資料(Satellite Information):
需要補充的是,在資料庫的聚集索引(Clustered Index)中,葉子節點直接包含衛星資料。在非聚集索引(NonClustered Index)中,葉子節點帶有指向衛星資料的指針。
第一次磁盤IO:
第二次磁盤IO:
第三次磁盤IO:
B-樹的範圍查找過程
自頂向下,查找到範圍的下限(3):
中序周遊到元素6:
中序周遊到元素8:
中序周遊到元素9:
中序周遊到元素11,周遊結束:
B+樹的範圍查找過程
自頂向下,查找到範圍的下限(3):
通過連結清單指針,周遊到元素6, 8:
通過連結清單指針,周遊到元素9, 11,周遊結束:
B+樹的特征:
1.有k個子樹的中間節點包含有k個元素(B樹中是k-1個元素),每個元素不儲存資料,隻用來索引,所有資料都儲存在葉子節點。
2.所有的葉子結點中包含了全部元素的資訊,及指向含這些元素記錄的指針,且葉子結點本身依關鍵字的大小自小而大順序連結。
3.所有的中間節點元素都同時存在于子節點,在子節點元素中是最大(或最小)元素。
B+樹的優勢:
1.單一節點存儲更多的元素,使得查詢的IO次數更少。
2.所有查詢都要查找到葉子節點,查詢性能穩定。
3.所有葉子節點形成有序連結清單,便于範圍查詢。