1、为什么使用索引
为尽量避免全表查询，因此使用索引来尽可能进行快速查找所需数据。
2、索引分类
聚簇索引（主键）：InnoDB 引擎生成（包含 frm、ibd 两种格式的文件），索引与记录均在节点上，无需回数据表查询，直接返回。
非聚簇索引：myisam（保护 frm、MYI、MYD 三种格式的文件），需回表查询数据后再返回，增加 I/O。
联合索引：多个字段组成，遵守最左原则，从左到右依次比较（前面的字段值相同才会使用后续字段比较），不会遗漏或跳过中间的任一索引字段。
3、数据库索引的数据结构
二叉树、平衡二叉树、Hash 树、B 树、B+ 树。
3.1、二叉树
节点既存索引，也存数据（记录或记录地址），各节点无冗余；
左边子节点小于父节点，右边子节点大于父节点，一个节点存单条记录。
不足：若索引字段的值自增的，则会造成该字段的索引搜索退化为链表查询，即可能会进行全表扫描。
3.2、平衡二叉树（红黑树）
节点既存索引，也存数据（记录或记录地址），各节点无冗余。
左边子节点小于父节点，右边子节点大于父节点，一个节点存单条记录。
优势：对索引存储结构进行了平衡，避免退化为全表扫描，各子树层级相差不超过两级。
不足：数据量大，树的深度深，则对应的磁盘 I/O 次数高，延迟时间长。
3.3、Hash 树
节点存储索引与数据，节点无冗余；
树深度为1，I/O 稳定。
不足：无法应用于范围查询。
3.4、B 树
节点既存索引，也存数据（记录或记录地址），个节点无冗余；
左边子节点小于父节点，右边子节点大于父节点，一个节点存多条记录，从左往右依次递增。
优势：单节点存多条记录，减少了树的深度，即相应减少了磁盘 I/O。
不足：若记录的内容存储量大，则单节点存储记录条数少，导致了深度也相应增大，对应的磁盘 I/O 也会增大。
3.5、B+ 树
节点只存储记录索引；
叶子节点包含所有索引及其数据（记录或记录地址），因此非叶子节点都是冗余数据；
左边子节点小于父节点，右边子节点大于父节点，一个节点存储多条记录，从左往右依次递增；
叶子节点之间有双向索引，因此叶子节点形成了双向链表，方便范围查询。
优势：非叶子节点只存储索引，因此容量大，存储索引条数多，树的深度浅，对应的磁盘 I/O 减少。
不足：数据量达到两千多万以上时，索引效率开始大幅度下滑，此时需要考虑分表，分库。
