Mysql索引原理

什么是索引？

一句话总结：索引是帮助Mysql快速高效获取数据的 排好序 的 数据结构；

索引常见的数据结构：

• 二叉树
• 红黑树
• Hash表
• B-Tree

数据库不用索引

如果我们数据库建表时不建索引直接查询，数据库只能遍历比较，时间复杂度为：O(n)；

二叉树

比如我们查询索引为10的数据，遵从树结构左小右大的原则，三次就可以查询出想要的索引，根据索引获取数据磁盘地址，时间复杂度为：O(log n);

但是二叉树有一个问题，如果从根节点是到叶子节点是顺序插入的话，二叉树就会变成一个线性的链表，这个时候和直接遍历数据没有区别，时间复杂度：O(n)；

这个时候我们思考一下，如果有一种平衡树，就可以提高效率，降低时间损耗，也就是下面的平衡二叉树（红黑树）；

红黑树

这个时候，时间复杂度就会一直为：O(log n);

但是我们还可以再思考一下，红黑树有没有问题呢？
肯定是有的，随着数据量的变大，树的高度会越来越高，我们查询的元素就越来越多，所以红黑树也是不行的；

我们继续思考，如果可以控制高度，是不是就解决了这个问题？
如果可以控制高度，将父节点的数据横向扩展，性能将会得到进一步的提升，这个时候B-Tree就登场了，其实我们的数据库索引就是基于B-Tree实现的；

B-Tree

B-Tree可以对树的每个节点做横向的扩展，既解决了链表问题，也保证树的高度不要太高，也就是每一个节点都存放索引和data，这种横向扩展的结构我们称做为页；

既然B-Tree这么完美，那为什么MySQL没有选择用B树做索引结构呢？
因为每个页里面都存放数据，带来了极大的IO开销，数据量如果很大，加载时内存损耗严重；

有什么办法可以解决吗？
如果我们只把数据存放在叶子节点上，父节点不存放数据，加载时根据父节点只加载某个叶子节点的数据，是不是就可以节省很多内存；B+Tree完全满足我们的想法；

B+Tree

B+Tree相较于B树有两个改变：

1. 将数据只存在在叶子节点上（冗余），非叶子节点不存储data，这样可以存放更多的索引；
2. 叶子节点包含所有的索引；
3. 叶子节点用指针连接，提高区间访问的性能；

数据存在叶子节点的好处？
根节点和中间节点就能存储更多的索引数据；

叶子节点的横向指针的好处？
叶子节点的横向指针可以支持范围查询，比如我们要查询上图中索引大于4的数据，只需要获取指针右边的所有数据就行，非常方便；

Hash

将索引通过散列算法以后存储，精确查询可以快速定位到数据地址；
但是有一个很严重的问题，不支持范围查找，因为hash运算以后的数据是没有顺序的，也不存在指针，所以无法进行范围查询；

聚簇索引和非聚簇索引

1. 叶子节点的data存放了实际数据的就是聚簇索引，反之是非聚簇索引；
2. 聚簇索引：innerDB就是聚簇索引的实现，叶子节点的data存放了实际数据；
3. 非聚簇索引：myisam就是非聚簇索引的实现，叶子节点的data只存放了数据的磁盘地址，想要真正定位到数据还要一次IO操作；

InnoDB表必须有主键，为什么推荐使用整形的自增主键？

1. 整形比较索引时方便；
2. 整形占用空间小；
3. 自增是为了防止分裂，减少树的自旋，降低性能开销；

关于设计表的几个建议

1. 建议使用innerDb引擎，支持事务、表锁、行锁、聚簇索引；
2. 最好有整形自增主键，强调一点根据数据量选用int或者bigint，尽量避免主键到头的尴尬；
3. 索引最好有唯一索引和复合索引搭配使用，不要滥建索引，会降低写的性能，树的旋转耗时；
4. 列字段占用空间越小越好，可以使用枚举来代替字符串；
5. 最好有create_time 和 update_time字段，方便定位问题；
6. 最好预留几个字段，方便扩展；
7. 字段备注越详细越好，方便后来者熟悉业务；
8. 数据表最好一次建好，后续执行DML会耗时，表越大越耗时，修改过程中会拒绝写操作；
9. 表字段不宜太多，可以垂直拆分成多个表；