為什麼Innodb選擇B+樹索引

語言: CN / TW / HK

B+樹結構 and 為什麼

資料結構演示網頁,可以通過網頁觀察資料結構的生成,更直觀的理解

索引結構預設使用B+樹,而不是二叉樹,紅黑樹,b樹,雜湊

為什麼?

什麼是索引

索引就是一種單獨的資料結構,用來對資料庫的資料進行快速檢索的資料結構,他針對某個表中的一列或者多列。

簡單的說就相當於圖書的目錄,你可以根據目錄快速找到自己想要的內容

二叉樹

每個根節點最多有兩個子節點

二叉搜尋樹 -- 左子樹小於根節點,右子樹大於父節點,二分搜尋的結構化

最好情況 -- logN

最壞情況 -- n

紅黑樹

自平衡的二叉搜尋樹

特性:

  • 每個節點都是黑色或者紅色的
  • 根節點是黑色的
  • 如果一個節點是紅色,他的子節點一定是黑色
  • 從一個節點到該節點所有葉子節點的路徑上包含相同資料的黑色節點
  • 所有葉子節點都是黑色的(葉子節點的值為null)

即使紅黑樹 也是一個二叉樹,隨著資料量的增多,紅黑樹的層級會越來越深,檢索速度會越來越慢

B-樹

紅黑樹是一個二叉樹,那B樹就是一個多叉樹,B樹每個節點有多個分支,即多叉樹

image-20220914113546000.png

特點:

  • 在B樹中,所有葉子結點和非葉子節點都會儲存資料!!
  • n階的B樹只能儲存n-1個key, n個指標
  • 一旦節點儲存的數量達到n,就會發生裂變,中間元素向上分裂

B+樹

B+樹是B樹的一個變種

image-20220914113732685.png

和B樹的區別:

  • 只有葉子結點才會儲存資料!!
  • 非葉子節點只會儲存索引
  • 葉子節點之間會形成一個連結串列,這個連結串列的所有元素都是有序排列的

Mysql的B+樹

Mysql對經典的B+樹進行了優化,在原有的基礎上,增加了指向相鄰葉子節點的指標,把一個單向的連結串列變成了雙向連結串列,這樣就更方便查找了

這種結構可以很方便進行範圍查詢和排序查詢

B+樹只有葉子結點儲存資料

image-20220914141738839.png

為什麼使用B+樹

需要結合Innodb的邏輯儲存結構來說,B+樹和B-樹的節點都儲存在一個頁上面,頁的大小是固定的

image-20220914142805900.png

  • 表空間
  • 區 -- 一個區有64頁, 大小1M
  • 頁 -- 一頁大小16k ,16 * 1024
  • 行 -- 資料是按行進行存放的

為什麼使用B+樹

  • 和二叉樹相比。B+樹層級更低,索引效率高

  • 和B樹相比。B樹和B+樹的索引的葉子節點都是儲存在一個頁上面的,而頁的大小是固定的。

  • B+樹的非葉子結點只儲存鍵值和指標,而B樹連帶資料一起儲存。這樣就導致相同大小的頁,使用B樹的鍵值和指標會變少,就會增加樹的高度,增加IO次數,導致效能降低
  • 和雜湊相比,B+樹支援範圍查詢,排序查詢,而雜湊不支援

思考題:

假設:一行資料大小為1k,一頁可以儲存16行這樣的資料。Innodb的指標佔用6個位元組的空間,鍵值採用BigInt,查8個位元組的空間,問能儲存多少資料

索引由鍵值和指標組成,n個鍵,n+1個指標

n*8 + (n+1) * 6 = 16 * 1024 , 計算得出 n = 1170

高度為2:

​ 1171 * 16 = 18736

高度為3

​ 1171 * 1171 * 16 = 21,939,856