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

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

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

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

聚族索引

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

非聚族索引

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

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

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

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