天天看點

第 12 章 多路查找樹第 12 章 多路查找樹

第 12 章 多路查找樹

1、二叉樹與 B 樹

1.1、二叉樹存在的問題

  • 二叉樹的操作效率較高,但是也存在問題, 請看下面的二叉樹
  • 二叉樹需要加載到記憶體的,如果二叉樹的節點少,沒有什麼問題,但是如果二叉樹的節點很多(比如1億), 就存在如下問題:
    • 問題1:在建構二叉樹時,需要多次進行i/o操作(海量資料存在資料庫或檔案中),節點海量,建構二叉樹時,速度有影響
    • 問題2:節點海量,也會造成二叉樹的高度很大,會降低操作速度
第 12 章 多路查找樹第 12 章 多路查找樹

1.2、多叉樹的基本介紹

  • 在二叉樹中,每個節點有資料項,最多有兩個子節點。如果允許每個節點可以有更多的資料項和更多的子節點,就是多叉樹(multiway tree)
  • 後面我們講解的2-3樹,2-3-4樹就是多叉樹,多叉樹通過重新組織節點,減少樹的高度,能對二叉樹進行優化
  • 舉例說明(下面2-3樹就是一顆多叉樹)
第 12 章 多路查找樹第 12 章 多路查找樹

1.3、B 樹的基本介紹

  • B樹通過重新組織節點,降低樹的高度,并且減少i/o讀寫次數來提升效率。
  • 如圖B樹通過重新組織節點, 降低了樹的高度。
  • 檔案系統及資料庫系統的設計者利用了磁盤預讀原理,将一個節點的大小設為等于一個頁(頁的大小通常為4k),這樣每個節點隻需要一次I/O就可以完全載入
  • 将樹的度M設定為1024,在600億個元素中最多隻需要4次I/O操作就可以讀取到想要的元素,B樹(B+)廣泛應用于檔案存儲系統以及資料庫系統中
第 12 章 多路查找樹第 12 章 多路查找樹

1.4、2-3 樹基本介紹

1.4.1、2-3 應用案例

  • 2-3樹是最簡單的B樹結構,具有如下特點:
    • 2-3樹的所有葉子節點都在同一層(隻要是B樹都滿足這個條件)
    • 有兩個子節點的節點叫二節點,二節點要麼沒有子節點,要麼有兩個子節點
    • 有三個子節點的節點叫三節點,三節點要麼沒有子節點,要麼有三個子節點
  • 2-3樹是由二節點和三節點構成的樹。
  • 2-3 樹插入規則:
    • 2-3樹的所有葉子節點都在同一層(隻要是B樹都滿足這個條件)
    • 有兩個子節點的節點叫二節點,二節點要麼沒有子節點,要麼有兩個子節點
    • 有三個子節點的節點叫三節點,三節點要麼沒有子節點,要麼有三個子節點
    • 當按照規則插入一個數到某個節點時,不能滿足上面三個要求,就需要拆,先向上拆,如果上層滿,則拆本層,拆後仍然需要滿足上面3個條件。
    • 對于三節點的子樹的值大小仍然遵守(BST 二叉排序樹)的規則
  • 将數列{16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20} 建構成2-3樹,并保證資料插入的大小順序,示範一下建構2-3樹的過程
    • 插入 24 時,構成二節點
      第 12 章 多路查找樹第 12 章 多路查找樹
    • 插入 12 時
      • 不能将其放在 16 的左邊,這樣就是四節點了。。。
      • 不能直接挂在 16 的左下位置,這樣就不滿足【2-3樹的所有葉子節點都在同一層】這個條件
      • 是以需要拆掉上一層的節點,将其重新組合成 2-3 樹
    第 12 章 多路查找樹第 12 章 多路查找樹
    • 插入 32 時,可直接放在 24 的右邊,構成一個三節點
    第 12 章 多路查找樹第 12 章 多路查找樹
    • 插入 26 時
      • 不能将其放在 24 的右邊,這樣就是四節點了。。。
      • 不能直接挂在 24 的右下位置,這樣就不滿足 B 樹的條件
      • 是以需要拆掉上一層的節點,将其重新組合成 2-3 樹
    第 12 章 多路查找樹第 12 章 多路查找樹
    • 插入 34 時
    第 12 章 多路查找樹第 12 章 多路查找樹
    • 插入 10 時
      • 當插入10時,應當在 10 - 12 -14 這個位置,但是這時滿了,是以向上層看, 16-26 也滿了
      • 是以将 10-12-14 拆 成 10 <-12->14 ,因為其它拆法,并不能滿足 二節點或三節點的要求
      • 但是這時,葉子節點沒有全部在同一層,需要調整 26 這個值到下面(如圖)
    第 12 章 多路查找樹第 12 章 多路查找樹
    • 插入 8 時
    第 12 章 多路查找樹第 12 章 多路查找樹
    • 插入 28 時
    第 12 章 多路查找樹第 12 章 多路查找樹
    • 插入 38 時
    第 12 章 多路查找樹第 12 章 多路查找樹
    • 插入 20 時
    第 12 章 多路查找樹第 12 章 多路查找樹

1.4.2、其他說明

  • 除了2-3 樹,還有 2-3-4 樹等,概念和 2-3 樹類似,也是一種B樹。 如圖:
第 12 章 多路查找樹第 12 章 多路查找樹

1.5、B樹的介紹

  • B-tree 樹即 B 樹,B 即 Balanced ,平衡的意思。有人把B-tree 翻譯成 B- 樹,容易讓人 産生誤解。會以為 B- 樹是一種樹,而 B 樹又是另一種樹。實際上,B-tree 就是指的 B 樹。
  • 前面已經介紹了2-3樹和2-3-4樹,他們就是B樹(英語:B-tree 也寫成B-樹),這裡我們再做一個說明,我們在學習Mysql時,經常聽到說某種類型的索引是基于B樹或者B+樹的,如圖
  • B樹的說明:
    • B樹的階(度):節點的最多子節點個數。比如2-3樹的階是3,2-3-4樹的階是4
    • B樹的搜尋,從根結點開始,對結點内的關鍵字(有序)序列進行二分查找,如果命中則結束,否則進入查詢關鍵字所屬範圍的兒子結點;重複,直到所對應的兒子指針為空,或已經是葉子結點
    • 關鍵字集合分布在整顆樹中,即葉子節點和非葉子節點都存放資料
    • 搜尋有可能在非葉子結點結束
    • 其搜尋性能等價于在關鍵字全集内做一次二分查找
第 12 章 多路查找樹第 12 章 多路查找樹

1.6、B+ 樹的介紹

  • B+樹是B樹的變體,也是一種多路搜尋樹。
  • B+樹的說明:
    • B+樹的搜尋與B樹也基本相同,差別是B+樹隻有達到葉子結點才命中(B樹可以在非葉子結點命中),其性能也等價于在關鍵字全集做一次二分查找
    • 所有關鍵字都出現在葉子結點的連結清單中(即資料隻能在葉子節點【也叫稠密索引】),且連結清單中的關鍵字(資料)恰好是有序的。
    • 不可能在非葉子結點命中
    • 非葉子結點相當于是葉子結點的索引(稀疏索引),葉子結點相當于是存儲(關鍵字)資料的資料層
    • B+樹的所有葉結點構成一個有序連結清單,可以按照關鍵碼排序的次序周遊全部記錄
    • B+樹更适合檔案索引系統,B樹和B+樹各有自己的應用場景,不能說B+樹完全比B樹好,反之亦然
第 12 章 多路查找樹第 12 章 多路查找樹
  • 自己對 B+ 樹的了解:
    • 就拿有序數列 { 8, 10, 12, 14, 16, 20, 24, 26, 28, 32, 34, 38 } 來說,如果連結清單形式存儲,搜尋效率肯定低得一匹
    • 但是有沒有什麼方法可以改進呢?一種就是前面所說的二叉樹,還有一種就是現在說的 B+ 樹
    • B+ 樹到底是什麼個意思?比如說我們想要查找 28 這個數,從前面挨個往後查找肯定是不行滴,但是我們知道 28 肯定是在 26 和 38 之間,有這個思路就可以了
    • 我們手動将 { 8, 10, 12, 14, 16, 20, 24, 26, 28, 32, 34, 38 } 分成幾個區間,查找 28 時,直接去他所在區間查不就快得多了嗎?這個所謂的區間,也就是我們常說的索引
第 12 章 多路查找樹第 12 章 多路查找樹

1.7、B* 樹的介紹

  • B* 樹是B+樹的變體,在B+樹的非根和非葉子結點再增加指向兄弟的指針。
  • B* 樹的說明:
    • B* 樹定義了非葉子結點關鍵字個數至少為(2/3)*M,即塊的最低使用率為2/3,而B+樹的塊的最低使用率為B+樹的1/2。
    • 從第1個特點我們可以看出,B* 樹配置設定新結點的機率比B+樹要低,空間使用率更高
第 12 章 多路查找樹第 12 章 多路查找樹

繼續閱讀