B 樹

B 樹

• 目錄：

  

• 一、衛星資料：
  • 指索引元素所指向的資料記錄，比如資料庫中的某一行。在B-樹中，無論非終端結點還是葉子結點都帶有衛星資料；在B+樹中隻有葉子結點帶有衛星資料，其餘非終端結點僅僅是索引，沒有任何資料關聯。
  • 在資料庫的聚集索引中，葉子結點直接包含衛星資料；在非聚集索引中，葉子結點帶有指向衛星資料的指針。
• 二、B- 樹
  • 定義：
    • 一種平衡的多路查找樹；
  • 使用場景：
    • 做檔案的索引，在檔案系統多使用；
  • 結構/特點：
    • 一棵m階的B-樹，或為空樹，或為滿足下列特性的m叉樹：
      • 1、樹中每個結點至多有m棵子樹；
      • 2、若根結點不是葉子結點，則至少有兩棵子樹；
      • 3、除根之外的所有非終端結點至少有[m/2]棵子樹；
      • 4、所有的非終端結點中包含下列資訊資料；
        • （n, A, K） n 關鍵字個數 k 為關鍵字 A 為指向子樹根結點的指針；
      • 5、所有的葉子 結點都出現在同一層次上，并且不帶資訊（實際上不存在，指向這些結點的指針為空）；
    • 例子：
      • m，階數是一個節點的子節點數目的最大值。
      • 4階的B-樹，深度為 4：

        

        • 可以看出，有一個頭指針，指向根結點；
        • 查找成功，結束；不繼續向下；
        • 查找失敗，如果順着指針查找，指針指向葉子結點，則說明該關鍵字不在此樹上。
  • 查找
    • 在B-樹上進行查找的過程是一個順時針查找結點和在結點的關鍵字中進行查找交叉進行的過程。
    • 在B-樹上查找包含兩個基本操作：
      • 1、在B-樹中找結點；
      • 2、在結點中找關鍵字。
      • B-樹通常存儲在磁盤上，前一查找操作是在磁盤上進行的，後以查找操作是在記憶體中進行的；即在磁盤上找到指針p所指結點後，先将結點信中的資訊存儲在記憶體中，然後再利用順序查找或者折半查找查詢等于K的關鍵字。
    • 決定B-樹查找效率的因素：
      • 在磁盤上查找的次數，即待查關鍵字所在結點在B-樹上的層次數。因為在磁盤上進行一次查找比在記憶體中進行一次查找耗費時間多得多。
    • 查找最壞的情況，即待查結點在B-樹上的最大層次數。也就是含N個關鍵字的M階B-樹的最大深度是多少。
• 三、B+ 樹
  • • B+ 樹是應檔案系統所需而出的一種B-樹的變型樹。
  • 使用場景
    • 為磁盤或其他直接存取輔助裝置而設計的一種平衡查找樹，在B+樹中，所有記錄結點都是按鍵值的大小的順序存放在同一層的葉子結點中，各葉子結點通過指針連接配接。
  • • m階的B-樹：
      • 1、有n棵子樹的結點中包含有n個關鍵字；
      • 2、所有的葉子結點中包含了全部關鍵字的資訊，及指向含有這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大順序連結。
      • 3、所有的非終端結點可以看成是索引部分，結點中僅含有其子樹（根結點）中的最大(或最小)關鍵字。
    • • 3階的B+樹

        

        • 從上圖得出的結論：
          • 1 、通常在B+樹上有兩個頭指針，一個指向根結點；一個指向關鍵字最小的葉子結點。
          • 2、葉子結點之間通過指針形成一個有序連結清單；
      • 單個查找：
  • • 兩種查找算法：
      • 1、從最小關鍵字起順序查找；
      • 2、從根結點開始，進行随機查找。
• 四、B+ 和B-樹，不同的是：
  • 1、若非終端結點上的關鍵字等于給定值，并不終止，而是繼續向下直到葉子結點。是以，在B+樹中，不管查找成功與否，每次查找都是走了一條從根到葉子結點的路徑。（穩定）；B-樹查找成功即停止；
  • 2、IO次數更少；
    • B+樹的非終端結點沒有衛星資料，故相同大小的磁盤頁可以容納更多的結點元素，意味着資料量相同的情況下，B+樹的結構比B-樹更加矮胖。
  • 3、範圍查詢更簡單；比如（3-9）
    • B-樹：查找到葉子結點大于等于3結束；（中序周遊）
    • B+樹： 從根結點開始查找到葉子結點大于等于3，然後通過葉子結點的連結清單進行查找。