MySQL B+樹索引效率為什么快

B+樹結(jié)構(gòu)

      Mysql 我們都知道他的存儲結(jié)構(gòu)是B+樹的格式，B+樹也是一個平衡二叉樹，和B樹的區(qū)別是，B+樹數(shù)據(jù)存儲在葉子節(jié)點B+樹 如下圖我這邊有1 ，2, 3，4, 5 五個數(shù)據(jù)B+樹的結(jié)構(gòu)存儲如下，這個五個數(shù)分別存儲在對應(yīng)的葉子節(jié)點上，分布在B+樹上面

      mysql索引查找算法是二分查找方式，時間復(fù)雜度是log（n） 如果我們要查找5這個數(shù)字，基于二分查找，先找到3根節(jié)點，因為5 > 3 從樹的右邊開始查 3 、4、5 基于二分查找找到4 然后對比4 > 5 找到5，整個過程經(jīng)歷了3次 IO操作就查找到了數(shù)據(jù)。mysql索引查找數(shù)據(jù)也就大部分情況下經(jīng)歷3次IO操作， 目前innodb存儲最小單位是頁，頁的最小單位容量是16kb，一個節(jié)點上面一頁數(shù)據(jù)16kb，如果我們一個索引key占用8個字符加上6個字符的指針，每一行數(shù)據(jù)占用1kb mysql存儲數(shù)量大概是 根節(jié)點-[（16*1024）/(8+6) ]*（第二層節(jié)點（16*1024）/(8+6) ）*16（第三層節(jié)點） = 21902400條數(shù)據(jù)，千萬級數(shù)據(jù)索引樹結(jié)構(gòu)只需要3層，查找只需要進行3次IO效率非常高，這些B+樹優(yōu)勢

聚族索引

  聚族索引類似/主鍵索引，索引行數(shù)據(jù)都放在葉子節(jié)點上面

非聚族索引

二級索引：通過兩次索引查找，葉子節(jié)點存放的是主鍵索引信息，再通過主鍵索引遍歷一次 IO 去查找對應(yīng)行數(shù)據(jù)

聯(lián)合索引：兩個字段聯(lián)合起來，存儲的是主鍵索引數(shù)據(jù)，不需要減少訪問B+ 樹的數(shù)量  

最左匹配原則 如 A B  C 三個字段索引

A  AB   ABC 三種索引類型有效，BC 無效