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 無效
