b+tree演進

語言: CN / TW / HK

innodb

大家都知道,mysql索引由儲存引擎層實現,常見的是innodb。

索引最主要得作用是提升訪問效率(類似於書籍目錄,比如新華字典,有字母索引,也有筆畫索引),索引的定義:

索引是對資料庫表中一列或多列的值進行排序的一種結構,使用索引可快速訪問資料庫表中的特定資訊

所以,索引是資料結構。

索引注意點

  • 建立索引要大量耗時(如果是大資料的情況,要慎重)
  • primary,唯一且不能為空。 fulltext index,一般不用
  • 不要使用隨機無序的欄位做索引(寫入會產生大量磁碟碎片,分裂問題和單鏈表一樣,導致大量操作)
  • 和業務無關的自增值當主鍵。
  • 不是所有儲存引擎都支援索引,也不是所有儲存引擎都是btree實現(但是主流是)
  • innodb 索引就是資料,資料就是索引(資料在葉子節點上)
  • 不要在離散度小的的資料列上建立索引
  • 聯合索引有最左匹配原則
  • 覆蓋索引,select key from table,key全部在索引中,避免了回表
  • 回表(二級索引查詢聚集索引(主鍵索引))
  • 聯合主鍵索引,看業務場景,一般不推薦用
  • 隨機無序的值,不適合主鍵索引

b+tree演進過程

分析其他演算法

二分查詢法,效率提升,但是陣列不好維護

連結串列,有侷限性,查詢鏈路過長

因此產生了二分查詢樹,binrary search tree (BST),並且天然有序。

二分查詢樹依舊擺脫不了樹深度問題(二叉樹問題),因此,平衡二叉樹出現。

一個節點只能存一個數據的話,會造成大量的頁浪費。

因此BTREE產生,一個樹節點的大小設計為16kb=>16384 bytes。一個節點儲存了 16384 / len(key) 個索引。

分裂、合併保持平衡和平衡二叉樹保持一致。

B+Tree非葉子節點只儲存索引,並且分為聚集索引和非聚集索引。非聚集索引的葉子節點儲存的是聚集索引的地址。聚集索引的葉子節點儲存的是實際儲存的值。

b+tree特性

  1. 關鍵字數量和度的數量是 N:N,樹的深度更小
  2. 只有葉子節點才有資料(io次數很穩定,就是樹的深度,並且使中間節點能存更多,能更矮更胖【樹形狀】)
  3. 葉子節點有雙向指標(遍歷資料更快,只需要從葉子節點最左邊開始即可)

一些其他question:

  1. 要是一行資料大於16k咋辦,一個page放不下怎麼辦,分裂成多個節點嗎?

https://gper.club/answers/7e7e7f7ff1g59gc0g6e 一步步來分析:

1)InnoDB Page預設大小為16KB = 16384 bytes,葉子節點最大為 16384 位元組。
2)如果一行資料的大小超過了page的可用空間,怎麼辦?比如一行資料包含了一個varchar欄位,varchar最大長度65536 bytes(實際是65532bytes),如果欄位達到這個長度,顯然一個page存不下這行資料
3)這個時候會發生行溢位( overflow pages),資料儲存在所謂的溢位頁(off-page)中
4)不同的行格式(row format)對於行溢位的處理不同 參考官網 https://dev.mysql.com/doc/refman/5.7/en/innodb-row-format.html 這裡有一篇中文的行格式的文章:https://www.cnblogs.com/25-lH/p/12739837.html 頁溢位確實會影響效能,儘量縮減欄位長度。
  1. 為什麼二級索引不存主鍵所在的葉子節點的地址呢?

聚集索引的樹可能會發生變化,存地址的話,不可靠,或者增加了維護性

  1. 沒有主鍵索引的時候怎麼辦?

_row_id,會自動建立一個索引

分享到: