對 B+ 樹與索引在 MySQL 中的認識

概述

本質：數(shù)據(jù)庫維護某種數(shù)據(jù)結構以某種方式引用（指向）數(shù)據(jù)

索引取舍原則：索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數(shù)

B樹

滿足的條件

d為大于1的一個正整數(shù)，稱為B-Tree的度

h為一個正整數(shù)，稱為B-Tree的高度

每個非葉子節(jié)點由n-1個key和n個指針組成，其中d《=n《=2d

每個葉子節(jié)點最少包含一個key和兩個指針，最多包含2d-1個key和2d個指針，葉節(jié)點的指針均為null

所有葉節(jié)點具有相同的深度，等于樹高h

key和指針互相間隔，節(jié)點兩端是指針

一個節(jié)點中的key從左到右非遞減排列

所有節(jié)點組成樹結構

每個指針要么為null，要么指向另外一個節(jié)點

一個度為d的B-Tree，設其索引N個key，則其樹高h的上限為logd（（N+1）/2），檢索一個key查找節(jié)點的個數(shù)的漸進復雜度為logd（N）

更新后的操作

插入刪除新的數(shù)據(jù)記錄會破壞B-Tree的性質，因此在插入刪除時，需要對樹進行一個分裂、合并、轉移等操作以保持B-Tree性質

B+樹

每個節(jié)點的指針上限為2d而不是2d+1

內節(jié)點不存儲data，只存儲key

葉子節(jié)點不存儲指針

在經典B+樹的基礎上，增加了順序訪問指針--》提高區(qū)間訪問的性能

為什么使用B/B+樹？

主存讀取

當系統(tǒng)需要讀取主存時，則將地址信號放到地址總線上傳給主存

主存讀到地址信號后，解析信號并定位到指定存儲單元，然后將此存儲單元數(shù)據(jù)放到數(shù)據(jù)總線上，供其它部件讀取

主存存取的時間僅與存取次數(shù)呈線性關系，因為不存在機械操作，兩次存取的數(shù)據(jù)的“距離”不會對時間有任何影響

磁盤存取原理

磁盤轉動，每個磁頭不動，負責讀取內容

不過已經有了多磁頭獨立技術

局部性原理

磁盤預讀：長度一般以頁的整數(shù)倍為單位

MyISAM索引實現(xiàn)

使用B+樹作為索引結構，data存放數(shù)據(jù)記錄的地址

索引文件與數(shù)據(jù)文件分離

主索引和輔助索引（Secondary key）在結構上沒有任何區(qū)別，只是主索引要求key是唯一的，而輔助索引的key可以重復

非聚集：MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，則取出其data域的值，然后以data域的值為地址，讀取相應數(shù)據(jù)記錄

.MYI文件的組成

整個索引文件的基本信息state

各索引的限制信息base

各索引的定義信息keydef

各索引記錄的概要信息recinfo

讀取索引的流程

query請求，直接讀取key cache中的cache block，有就返回

沒有就到.MYI文件中以file block方式讀取數(shù)據(jù)

再以相同的格式存取key cache

再將key cache中的數(shù)據(jù)返回

InnoDB索引實現(xiàn)

也是使用B+樹

第一個與MyISAM的不同點

第一個重大區(qū)別是InnoDB的數(shù)據(jù)文件本身就是索引文件，表數(shù)據(jù)文件本身就是按B+Tree組織的一個索引結構

InnoDB的數(shù)據(jù)文件本身要按主鍵聚集

所以InnoDB要求表必須有主鍵（MyISAM可以沒有）

沒有顯式指定，自動選擇唯一標識列

不存在的話，生成6個字節(jié)長整型的隱含字段

第二個與MyISAM的不同點

InnoDB的輔助索引data域存儲相應記錄主鍵的值而不是地址

換句話說，InnoDB的所有輔助索引都引用主鍵作為data域

輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄

得出的優(yōu)化點

不建議使用過長的字段作為主鍵，因為所有輔助索引都引用主索引，過長的主索引會令輔助索引變得過大

用非單調的字段作為主鍵在InnoDB中也不好，因為InnoDB數(shù)據(jù)文件本身是一顆B+Tree，非單調的主鍵會造成在插入新記錄時數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調整，十分低效，而使用自增字段作為主鍵就很不錯了

聚簇索引鍵被更新造成的成本除了索引數(shù)據(jù)可能會移動，相關的所有記錄數(shù)據(jù)也要移動

索引使用策略及優(yōu)化

全列匹配

按照索引中所有列進行精確匹配（這里精確匹配指“=”或“IN”匹配）時，索引可以被用到

理論上索引對順序是敏感的，但是由于MySQL的查詢優(yōu)化器會自動調整where子句的條件順序以使用適合的索引

最左前綴匹配

當查詢條件精確匹配索引的左邊連續(xù)一個或幾個列時，索引可以被用到

查詢條件用到了索引中列的精確匹配，但是中間某個條件未提供

只能用到索引中，從中間斷開前的列

應對

可以增加輔助索引

當中間條件選項較少時，用隔離列的方式，使用IN包含

看情況，比較建立

查詢條件沒有指定索引第一列

不滿足使用索引的條件

匹配某列的前綴字符串

可以使用索引

如果通配符%不出現(xiàn)在開頭，則可以用到索引，但根據(jù)具體情況不同可能只會用其中一個前綴

范圍查詢

范圍列可以用到索引（必須是最左前綴），但是范圍列后面的列無法用到索引

同時，索引最多用于一個范圍列，因此如果查詢條件中有兩個范圍列則無法全用到索引

僅用explain可能無法區(qū)分范圍索引和多值匹配

查詢條件中含有函數(shù)/表達式

一般不使用哦

手工算好再代入

索引選擇性與前綴索引

MyISAM與InnoDB基數(shù)統(tǒng)計方式

MyisAM索引的基數(shù)值（Cardinality，show index 命令可以看見）是精確的，InnoDB則是估計值

MyisAM統(tǒng)計信息是保存磁盤中，在alter表或Analyze table操作更新此信息

而InnoDB則是在表第一次打開的時候估計值保存在緩存區(qū)內

不建議建立索引的情況

表記錄比較少

索引的選擇性低：不重復的索引值（也叫基數(shù)，Cardinality）與表記錄數(shù)（#T）的比值

前綴索引

用列的前綴代替整個列作為索引key，當前綴長度合適時，可以做到既使得前綴索引的選擇性接近全列索引，同時因為索引key變短而減少了索引文件的大小和維護開銷

缺點

不能用于ORDER BY和GROUP BY操作

也不能用于Covering index（即當索引本身包含查詢所需全部數(shù)據(jù)時，不再訪問數(shù)據(jù)文件本身）

InnoDB主鍵選擇與插入優(yōu)化

如果沒有特別的需要，請永遠使用一個與業(yè)務無關的自增字段作為主鍵

InnoDB使用聚集索引，數(shù)據(jù)記錄本身被存于主索引（一顆B+Tree）的葉子節(jié)點上

這就要求同一個葉子節(jié)點內（大小為一個內存頁或磁盤頁）的各條數(shù)據(jù)記錄按主鍵順序存放，因此每當有一條新的記錄插入時，MySQL會根據(jù)其主鍵將其插入適當?shù)墓?jié)點和位置，如果頁面達到裝載因子（InnoDB默認為15/16），則開辟一個新的頁（節(jié)點）

如果使用非自增主鍵，每次插入近似隨機，容易引起數(shù)據(jù)的移動，重新讀目標頁面，碎片也多了，雖然也可以用OPTIMIZE TABLE重建優(yōu)化，但麻煩啊

參考資料

圖片來源網絡

《高性能MySQL》

作者：AnnsShadoW

https://www.cnblogs.com/annsshadow/p/5355090.html

編輯：jq