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