为什么要使用索引

为了避免全表扫描，加快数据的查询速度

什么样的信息能成为索引

主键、唯一键以及普通键等

索引的数据结构

• 生成索引，建立二叉查找树进行二分查找
• 生成索引，建立B-Tree结构进行查找
• 生成索引，建立B+-Tree结构进行查找
• 生成索引，建立Hash结构进行查找

B-Tree

B-Tree.png

定义

• 根节点至少包含两个孩子
• 树中每个节点最多含有m个孩子（m >= 2）
• 除根节点和叶节点外，其他每个节点至少有cell(m/2)个孩子
• 所有叶子节点都位于同一层

B+-Tree

B+-Tree.png

定义

B+树是B树的变体，其定义基本与B树相同，除了：

• 非叶子节点的子树指针与关键字个数相同
• 非叶子节点的子树指针P[i]，指向关键字值[K[i],K[i+1])的子树
• 非叶子节点仅用来索引，数据都保存在叶子节点中
• 所有叶子节点均有一个链指针指向下一个叶子节点，并按大小顺序链接

B+树更适合做存储索引

• B+树的磁盘读写代价更低
• B+树的查询效率更加稳定O(logn)
• B+树更有利于对数据库的扫描

Hash索引

缺点

• 仅仅能满足“=”，“IN”，不能使用范围查询
• 无法被用来避免数据的排序操作
• 不能利用部分索引键查询
• 不能避免表扫描
• 遇到大量Hash值相等的情况后性能并不一定就会比B+树索引高

稀疏索引和密集索引

• 密集索引文件中每个搜索码值都对应一个索引值（包不仅保存键值，还保存其他列信息）
• 稀疏索引文字只为索引码的某些值建立索引项（只有键位信息和该行地址）

Mysql—InnoDB

• 若一个主键被定义，该主键则作为密集索引
• 若没有主键被定义，该表的第一个唯一非空索引则作为密集索引
• 若不满足以上条件，InnoDB内部会生成一个隐藏主键（密集索引）
• 非主键索引存储相关键位值和其对应的主键值，包含两次查找

通过稀疏索引查找到主键，然后密集索引找到具体数据

根据索引查找.png

InnoDB数据和索引在同一个文件中
MyISAM数据在一个文件中，索引在一个文件中