Titan專欄

用文字來整理生命

BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

44 隨筆 :: 49 文章 :: 19 評論 :: 0 Trackbacks

<

2025年6月

>

日

一

二

三

四

五

六

25

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

常用鏈接

留言簿(7)

隨筆檔案(44)

文章分類(49)

文章檔案(49)

搜索

閱讀排行榜

評論排行榜

B+樹的研究

1、B+樹索引的總體結構
①B⁺樹索引是一個多級索引，但是其結構不同于多級順序索引；
②B⁺樹索引采用平衡樹結構，即每個葉結點到根的路徑長度都相同；
③每個非葉結點有到n個子女，n對特定的樹是固定的；
④B⁺樹的所有結點結構都相同，它最多包含n-1個搜索碼值K1、K2、…、Kn-1，以及n個指針P1、P2、…、Pn，每個結點中的搜索碼值按次序存放，即如果i<j，那么Ki<Kj，如圖8-3-1所示。

圖8-3-1：B⁺樹的結點結構

2、B⁺樹索引的葉結點
①指針Pi(i=1,2,…,n-1)指向具有搜索碼值Ki的一個文件記錄或一個指針（存儲）桶，桶中的每個指針指向具有搜索碼值Ki的一個文件記錄。指針桶只在文件不按搜索碼順序物理存儲時才使用。指針Pn具有特殊的作用；
②每個葉結點最多可有n-1個搜索碼值，最少也要有

個搜索碼值。各個葉結點中搜索碼值的范圍互不相交。要使B+樹索引成為稠密索引，數據文件中的各搜索碼值都必須出現在某個葉結點中且只能出現一次；
③由于各葉結點按照所含的搜索碼值有一個線性順序，所以就可以利用各個葉結點的指針Pn將葉結點按搜索碼順序鏈接在一起。這種排序能夠高效地對文件進行順序處理，而B⁺樹索引的其他結構能夠高效地對文件進行隨機處理，如圖8-3-2所示。

圖8-3-2：B+樹索引的葉結點結構示例

3、B⁺樹索引的非葉結點
①B⁺樹索引的非葉結點形成葉結點上的一個多級（稀疏）索引；
②非葉結點的結構和葉結點的結構相同，即含有能夠存儲n-1個搜索碼值和n個指針的存儲單元的數據結構。只不過非葉結點中的所有指針都指向樹中的結點；
③如果一個非葉結點有m個指針，則

≤m≤n。若m<n，則非葉結點中指針Pm之后的所有空閑空間作為預留空間，與葉結點的區別在于結點的最后一個指針Pm和Pn的位置與指向不同，如圖8-3-3所示；

圖8-3-3：B+樹索引的非葉結點結構

④在一個含有m個指針的非葉結點中，指針Pi(i=2,…,m-1)指向一棵子樹，該子樹的所有結點的搜索碼值大于等于Ki-1而小于Ki。指針Pm指向子樹中所含搜索碼值大于等于Km-1的那一部分，而指針P1指向子樹中所含搜索碼值小于K1的那一部分，如圖8-3-4所示。

圖8-3-4：B⁺樹索引的非葉結點中指針Pi的指向

4、B⁺樹索引的根結點
①根結點的結構也與葉結點相同；
②根結點包含的指針數可以小于

。但是，除非整棵樹只有一個結點，否則根結點必須至少包含兩個指針。圖8-3-5給出一個B⁺樹結構的示意圖。

圖8-3-5：account關系的B⁺樹索引結構

posted on 2006-02-12 23:12 Titan 閱讀(3796) 評論(0) 編輯收藏所屬分類: 索引調優

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: B+樹的研究基于索引的SQL語句優化之降龍十八掌 [轉]B-tree algorithms ORACLE索引與高性能SQL介紹關于三種JOIN的理解 SQL語句主要的連接方法 [轉載]Effective SQL

Titan專欄

常用鏈接

留言簿(7)

隨筆檔案(44)

文章分類(49)

文章檔案(49)

相冊

國外經典

好友

技術測試

技術鏈接

搜索

最新評論

閱讀排行榜

評論排行榜