索引是排好序的数据结构
1 索引数据结构
- hash索引、二叉树、平衡二叉树、B-Tree、B+Tree
- 数据结构在线示例：点击跳转
2 索引类型
2.1 聚簇索引
又叫“聚集索引” ，索引和数据存储在一起
2.2 非聚簇索引
又叫“非聚集索引” ，索引和数据分开存储
3 InnoDB存储引擎的索引
- 表数据文件本身是按B+Tree组织的一个索引结构文件
- 聚簇索引-叶节点包含完整的数据
- 叶子节点保存全部(列)数据
- 非叶子节点仅保存索引
3.1 设计与常见规范
3.1.1 推荐表中包含整型自增主键
建议Innodb表必须包含主键，并且推荐使用整型的自增主键
- 整型字段占用的更小的空间，可以节约磁盘；
- 整型字段更方便进行数据比对，而字符串比较时需要逐位比较，效率相对低一些；
- 自增是为了避免节点分裂，导致插入、更新数据性能降低；
3.1.2 推荐使用自增主键
- 依次插入：1、3、5、7、9、10、11、12、13、14
- 当继续插入：2、4之后，树进行了分裂,分裂效果图如下
- 可以看出，如果是连续自增的ID，则默认会追加新的节点，不会导致节点大规模的分裂
- 如果插入不连续的ID，会导致原先的节点分裂，影响整体的性能
3.1.3 二级索引叶子节点存储主键值
保证数据一致性，节省存储空间；
具体参考如下图的区别：图3.4 聚簇索引-主键索引、图3.4.2 非聚簇索引-联合主键
3.2 Hash索引
- 对索引的Key进行一次hash计算就可以定位出数据存储的位置
- 很多时候Hash索引要比B+Tree索引效率更高效
- 仅能满足=、in，不支持范围查询
- Hash冲突，需要额外使用链表解决
3.3 B-Tree索引
- 叶节点具有相同的深度，叶节点的指针为空
- 所有索引元素不重复
- 节点中的数据索引从左到右递增排列
3.4 B+Tree(特指Mysql的B+Tree)
- 非叶子节点不存在data，只存储索引(冗余索引)，可以存放更多的索引
- 叶节点包含所有索引字段
- 叶子节点用双向指针链接，提高区间访问的性能
- 普通的B+Tree的叶子结点之间仅存在单向指针，而mysql对B+Tree做了优化升级，支持双向指针，提升区间之间的数据访问效率
3.4.1 非聚簇索引-联合主键
3.4.2 非聚簇索引-联合索引
