MySQL學習17_索引B+樹

樹

• 無序樹：任意節點的子節點之間沒有任何的順序關系，稱之為無序樹，也叫自由樹
• 有序樹：子節點之間由順序關系 二叉樹：每個節點最多含有兩個子樹的樹 完全二叉樹：若一棵樹的深度為d，除去第d層外，其他各層的節點數目達到了最大值，且第d層所有節點從左向右連續緊密的排列的二叉樹 滿二叉樹：所有層的節點數達到了最大數 平衡二叉樹：當且僅當任何節點之間的兩顆子樹的高度差不大于1的二叉樹 排序二叉樹：二叉搜尋樹，二叉查找樹，性質：任何節點左邊的數比節點上的數小，右邊比節點上的數大 霍夫曼樹：用于資訊編碼 B樹/B^+樹：在MySQL的索引中使用

應用場景

• HTML檔案
• 路由協定
• mysql索引
• 檔案目錄的目錄結構
• AI算法都是樹搜尋，比如決策樹

樹的周遊

層次周遊是從上到下，從左到右周遊的方式

深度周遊的三種周遊順序（左節點一定在右節點前面）：

如何通過周遊結果反推樹的結構（必須給出中序周遊）

隻有給定中序才能将左、右子樹分開

# 反推demo

# 前：0,1,3,7,8,4,9,2,5,6
# 中：7,3,8,1,9,4,0,5,2,6           

複制

• 前序周遊：

  根左右

  規則确定第一個是根節點為0
• 中序周遊：
  • 根據根節點0，将中序結果分成三部分：

    7,3,8,1,9,4 + 0 + 5,2,6

  • 是以在中序周遊結果中，左子樹：738194 ；右子樹：526
• 前序周遊：根據上步，分成三部分：

  0+1,3,7,8,4,9+2,5,6

  ；左子樹：

  1,3,7,8,4,9

  ；右子樹：

  2,5,6

  • 左子樹：

    1,3,7,8,4,9

    ，左根節點是1
  • 右子樹：

    2,5,6

    ，右根節點是2
• 中序周遊：根據上步，确定了三個根節點，将中序結果分成多塊：

  7,3,8 + (1) + 9,4 + (0) + 5 + (2) + 6

  • 左子樹：

    7,3,8 + (1) + 9,4

    中根據中序的

    左根右

    規則，7,3,8是左子樹，9,4為右子樹
    • 根據

      左根右

      規則，依次對應：

      左7根3右8

      ；94中9是左子樹，根是4
  • 右子樹：

    5 + (2) + 6

    ，5是左節點，6是右節點

索引

索引是加速

MySQL

對表中資料行的高效擷取而建立的一種分散存儲的資料結構，正确地建立合适的索引作用是提高資料查詢性能的基礎。

B+樹查詢時間，樹的高度有關

• 平均查詢時間是O(logn)
• 哈希存儲索引O(1)

圖解MySQL索引

索引實作

mysql

預設存儲引擎

innodb

隻顯式支援B-Tree( 從技術上來說是B+Tree)索引。

對于頻繁通路的表，

innodb

會透明建立自适應hash索引，即在B樹索引基礎上建立hash索引，可以顯著提高查找效率，對于用戶端是透明的，不可控制的，隐式的。

哈希索引

基于哈希表實作。存儲引擎會對所有的列計算一個哈希碼， Hash索引将所有的哈希碼存儲在索引中，同時在索引表中儲存指向每個資料行的指針

B+ Tree

B樹是一種多路搜尋樹，每個節點可以擁有多于兩個子節點。M路的B樹最多擁有M個子節點。 B+樹中的B代表平衡（balance），而不是二叉（binary），因為B+樹是從最早的平衡二叉樹演化而來的。

二叉查找樹

• 左節點小于根節點
• 右節點大于根節點