天天看點

樹形索引(B+樹)

一棵m階的B+樹和m階的B-樹的異同點在于:

      1.有n棵子樹的結點中含有n 個關鍵字,即每個關鍵碼對應一顆子樹

      2.所有的終端結點中包含了全部關鍵字的資訊,及指向含有這些關鍵字記錄的指針,且終端結點本身依關鍵字的大小自小而大的順序連結。 (而B- 樹的葉子節點并沒有包括全部需要查找的資訊)

      3.所有的非終端結點可以看成是索引部分,結點中僅含有其子樹根結點中最大(或最小)關鍵字。 (而B- 樹的非終節點也包含需要查找的有效資訊)

      4.所有外結點均不是空指針,而是作為指向關鍵碼所對應記錄在檔案中的位置指針。

由于在m階B+樹中,每個結點最多有m棵子樹,故,m階B+樹的結點所含關鍵碼的最大個數為m,而在m階B-樹的結點中所含關鍵碼的最大個數為m-1.m階B+樹的結點所含關鍵碼的個數n的最大值可為m。

        (1)根結點隻有1個,分支數量範圍[2,m]。

        (2)除根以外的非葉子結點,每個結點包含分支數範圍[[m/2],m],其中[m/2]表示取大于m/2的最小整數(向上取整)

        (3)所有非葉子節點的關鍵字數目等于它的分支數量。

        (4) 所有葉子節點都在同一層,且關鍵字數目範圍是[[m/2],m],其中[m/2]表示取大于m/2的最小整數。

        (5)所有非葉子節點的關鍵字可以看成是索引部分,這些索引等于其子樹(根結點)中的最大(或最小)關鍵字。例如一個非葉子節點包含資訊: (n,A1,K1, A2,K2,……,An,Kn),其中Ki為關鍵字,Ai為指向子樹根結點的指針,n表示關鍵字個數。即Ai所指子樹中的關鍵字均小于或等于Ki,而Ai+1所指的關鍵字均大于Ki(i=1,2,……,n)。

        (6)葉子節點包含全部關鍵字的資訊(非葉子節點隻包含索引),且葉子結點中的所有關鍵字依照大小順序連結(是以一個B+樹通常有兩個頭指針,一個是指向根節點的root,另一個是指向最小關鍵字的sqt)。

樹形索引(B+樹)

B+樹

查找:在B+樹上查找時,若在非終端結點上有關鍵碼等于給定值,并不終止,而是繼續向下直到終端結點。是以,在B+樹上不管查找成功與否,每次查找都是走了一條從根節點到終端結點的路徑。

插入:B+樹插入僅在終端節點上進行,當終端節點中關鍵碼個數大于m時要分裂成兩個結點(插入後含m+1個關鍵碼):若m為奇數,則分裂所得兩個結點所含關鍵碼個數均為(m+1)/2;若m偶,則分為m/2和m/2+1個。它們雙親結點中應同時包含這兩個節點中的最大關鍵碼。

樹形索引(B+樹)

在深度大于1的B+樹上插入一個比根節點上最大關鍵碼還要大的關鍵碼時,為不破壞B+樹特性:将根至終端結點路徑上結點(不包括終端結點)中的原最大關鍵碼改為新插入的較大關鍵碼,而僅在終端結點中将新插入的較大關鍵碼加在原最大關鍵碼之後,然後檢查終端結點是否滿足m階B+樹定義要求。若加入後,關鍵碼個數仍小于或等于m,則不需分裂結點,若加入後終端結點中關鍵碼個數為m+1,則對該終端結點進行分裂-提升操作。

删除:僅在終端結點進行。當終端結點最大關鍵碼被删,則在非終端結點中的值(即為該最大關鍵碼)可作為一個“分界關鍵碼”存在。若為B+樹的組織嚴格,可将次大關鍵碼提升到其父結點代替原來的最大關鍵碼,進一步上傳直至根結點。若因删除,使結點中關鍵碼個數少于[m/2],進行合并操作。

B+樹特适合範圍查找。一旦找到範圍中第一個關鍵碼及記錄,就可在該終端結點或順着該終端結點往後的連接配接指針,根據範圍的上界值,快速找出所給範圍内的所有關鍵碼及記錄。

用途:B+ 樹通常用于資料庫和作業系統的檔案系統中。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等檔案系統都在使用B+樹作為中繼資料索引。B+ 樹的特點是能夠保持資料穩定有序,其插入與修改擁有較穩定的對數時間複雜度。B+ 樹元素自底向上插入。

B+樹主要用于磁盤,拆分意味着磁盤的操作,應該在可能的情況下盡量減少頁的拆分。

樹形索引(B+樹)
樹形索引(B+樹)

繼續閱讀