MySQL索引与b+树浅析

1.什么是索引

索引是为了加速对表中的数据检索而创建的一种数据结构（比如二叉搜索树）。索引一般以文件的形式存储在磁盘上，所以使用时需要进行磁盘IO。

2.索引的优缺点

优点：

1. 索引能极大的减少要扫描的数据量。在查询某条数据时，如果不使用索引，则需要对所有数据进行依次遍历。
2. 索引能把随机IO变为顺序IO。磁盘IO的效率是很低的，而随机IO又比顺序IO更低（因为随机IO磁头需要更多的移动），使用索引大部分情况下会要求连续的存储空间，减少随机IO。
3. 索引能加速排序和分组。索引能快速定位数据，同时索引默认是升序构建的，能减少排序和分组的时间开销。

缺点：

1. 占用磁盘空间。
2. 对数据进行更新、修改、删除时，需要修改索引。特别是主键不是递增的插入，很容易造成页分裂，影响数据库性能。
3. 当二级索引的索引列重复项过多时，使用二级索引查询的数据量就会过多，造成大量回表，性能可能不如全表扫描。
4. 在查询前，需要生成执行计划，需要计算使用不同索引的执行成本。因此，如果索引建立太多，不仅维护成本高，还可能影响查询效率。

3.磁盘存取

为什么磁盘读写慢、为什么顺序io要比随机io快，我们要先对磁盘有所了解

磁盘存取有以下特点：

• 寻道时间：磁头找到指定的磁道花费的时间，速度慢
• 旋转时间：磁头找到磁道上对应的扇区的时间，速度较快
• 预读：磁盘读取数据时会提前缓存其周围长度为页的整数倍的数据到内存中
• 空间连续性原理：被访问的数据，其周围的数据有更高的可能性被访问

因为存在机械运动，磁盘存取的效率综合相比内存来说是很低的。innodb在设计上就在尽量减少磁盘io，并尽量减少随机io。

4.b+树

b+树每个节点都是一页，非叶子节点存储主键和子节点地址（就像一本书的目录），叶子节点存储数据。

查找的时候根据主键定位到对应的叶子节点，从而获取到需要的数据。

4.1为什么使用b+树作为存储结构

• b+树的非叶子节点只存储目录项，占用空间小，所以一页可以存储更多的目录信息，整体的树的高度较低，能够有效减少IO次数。
• 多路平衡查找树，叶子节点顺序排列，并使用双向链表关联，在范围查找和排序查找上性能更好

4.2不同类型索引

聚簇索引即根据主键建立的b+树结构，叶子节点存储了所有数据

非聚簇索引即b+树叶子节点不存储全部数据，只存储索引列和指向真实数据地址的指针，

二级索引以非主键列建立的b+树结构，叶子节点存储的是主键和索引列的信息

前缀索引即以字符串的前面n个字符来构建索引，能减小索引占用的存储空间，但会导致无法使用索引覆盖（即便只查询索引列，也要回表获取到索引列的完整信息）

4.3回表

什么是回表

回表即查询时根据二级索引获取到符合条件的主键值，再根据主键值到聚簇索引中查找完整的列信息。

因为如果查询使用的是二级索引，查询需要的信息可能在二级索引上没有，所以需要回到聚簇索引获取到对应信息。

问题：如果不使用主键索引，一定会回表吗？

不一定，如果需要查询的列只包括主键或索引列，那么仅通过查询二级索引就能获得需要的信息，就不需要回表了。这也被称作覆盖索引

5.一些问题

• innodb如何查询数据

  没有索引：如果查询条件不涉及到索引，那么会进行全表扫描，从第一页开始沿着链表遍历。

  主键索引：查聚簇索引，效率高

  二级索引：如果使用了覆盖索引，效率高；如果需要回表，效率低一些

• 表的主键选择

  最好使用自增id作为主键，这样索引维护成本低，不会因为页分裂造成索引树的频繁变动，因为数据永远是往最后一页插入。不建议使用uuid这类随机字符串，因为插入位置不确定，如果插入位置位于一个已经满了的页的后面，则需要对该页进行分裂操作，构建一个新的页，b+树涉及到的目录项也要更新，整个过程复杂许多。

• 唯一索引与普通索引的比较

  查找：唯一索引直接定位到满足条件的记录；普通索引在定位到第一条满足条件的记录后还会向后查找。这之间的性能差距忽略不计

  更新：唯一索引将数据页读入内存，判断是否产生冲突并写入更新；普通索引将更新记录在change buffer中，等下次需要读取数据时再进行更新。相比之下普通索引更新性能要好些，但change buffer适用于写多读少的场景，如果写完后立刻读还不如直接将更新写入磁盘。

  总的来说，两种索引查询没什么区别，从更新效率考虑，推荐使用普通索引，但也要承担change buffer带来的风险
  e buffer适用于写多读少的场景，如果写完后立刻读还不如直接将更新写入磁盘。