為什么要使用索引
為了避免全表掃描，加快數(shù)據(jù)的查詢速度
什么樣的信息能成為索引
主鍵蔗候、唯一鍵以及普通鍵等
索引的數(shù)據(jù)結(jié)構(gòu)
- 生成索引市埋，建立二叉查找樹進(jìn)行二分查找
- 生成索引，建立B-Tree結(jié)構(gòu)進(jìn)行查找
- 生成索引绊含，建立B+-Tree結(jié)構(gòu)進(jìn)行查找
- 生成索引，建立Hash結(jié)構(gòu)進(jìn)行查找
B-Tree
B-Tree.png
定義
- 根節(jié)點(diǎn)至少包含兩個(gè)孩子
- 樹中每個(gè)節(jié)點(diǎn)最多含有m個(gè)孩子（m >= 2）
- 除根節(jié)點(diǎn)和葉節(jié)點(diǎn)外炊汹，其他每個(gè)節(jié)點(diǎn)至少有cell(m/2)個(gè)孩子
- 所有葉子節(jié)點(diǎn)都位于同一層
B+-Tree
B+-Tree.png
定義
B+樹是B樹的變體躬充，其定義基本與B樹相同，除了：
- 非葉子節(jié)點(diǎn)的子樹指針與關(guān)鍵字個(gè)數(shù)相同
- 非葉子節(jié)點(diǎn)的子樹指針P[i]讨便，指向關(guān)鍵字值[K[i],K[i+1])的子樹
- 非葉子節(jié)點(diǎn)僅用來(lái)索引充甚，數(shù)據(jù)都保存在葉子節(jié)點(diǎn)中
- 所有葉子節(jié)點(diǎn)均有一個(gè)鏈指針指向下一個(gè)葉子節(jié)點(diǎn)，并按大小順序鏈接
B+樹更適合做存儲(chǔ)索引
- B+樹的磁盤讀寫代價(jià)更低
- B+樹的查詢效率更加穩(wěn)定O(logn)
- B+樹更有利于對(duì)數(shù)據(jù)庫(kù)的掃描
Hash索引
缺點(diǎn)
- 僅僅能滿足“=”霸褒，“IN”伴找，不能使用范圍查詢
- 無(wú)法被用來(lái)避免數(shù)據(jù)的排序操作
- 不能利用部分索引鍵查詢
- 不能避免表掃描
- 遇到大量Hash值相等的情況后性能并不一定就會(huì)比B+樹索引高
稀疏索引和密集索引
- 密集索引文件中每個(gè)搜索碼值都對(duì)應(yīng)一個(gè)索引值（包不僅保存鍵值，還保存其他列信息）
- 稀疏索引文字只為索引碼的某些值建立索引項(xiàng)（只有鍵位信息和該行地址）
Mysql—InnoDB
- 若一個(gè)主鍵被定義废菱，該主鍵則作為密集索引
- 若沒(méi)有主鍵被定義技矮，該表的第一個(gè)唯一非空索引則作為密集索引
- 若不滿足以上條件抖誉，InnoDB內(nèi)部會(huì)生成一個(gè)隱藏主鍵（密集索引）
- 非主鍵索引存儲(chǔ)相關(guān)鍵位值和其對(duì)應(yīng)的主鍵值，包含兩次查找
通過(guò)稀疏索引查找到主鍵衰倦，然后密集索引找到具體數(shù)據(jù)
根據(jù)索引查找.png
InnoDB數(shù)據(jù)和索引在同一個(gè)文件中
MyISAM數(shù)據(jù)在一個(gè)文件中袒炉，索引在一個(gè)文件中
