索引的本质

索引是帮助MySQL高效获取数据的 排好序 的 数据结构

索引的数据结构

下面介绍几种数据结构,先有个影响。mysql索引支持B+树 和 hash。

二叉树

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。但是对于单边增长的数据没有性能提升 最后相当于链表。

红黑树

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。红黑树不是一个平衡树 左右节点会存在高度差

Hash

对索引的key进行一次hash计算就可以定位出数据存储的位置，很多时候Hash索引要比B+ 树索引更高效但是仅能满足 “=”，“IN”，不支持范围查询并存在hash冲突问题。

BTree

叶节点具有相同的深度，叶节点的指针为空,所有索引元素不重复,节点中的数据索引从左到右递增排列。但是对区间访问的能力不足。

B+Tree

非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引，叶子节点包含所有索引字段,叶子节点用指针连接，提高区间访问的性能。

为什么说B+比B树更适合实际应用中操作系统的文件索引和数据库索引？

1. B+的磁盘读写代价更低。

   B+的内部结点并没有指向关键字具体信息的指针，因此其内部结点相对B树更小。
   如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

2. B+-tree的查询效率更加稳定。

   由于非叶子节点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

索引类别

聚集索引

索引树叶子结点包含完整的数据（InnoDB主键索引）

非聚集索引

索引文件和数据文件是分离的 索引树叶子节点存储的是数据文件中数据对应的磁盘地址(MyschemaDB)，需要回表操作

存储引擎

数据库最终的数据都是落在磁盘上，mysql的存储引擎是可插拔的，有能力的话自己也可以实现一个存储引擎.不同存储引擎它在磁盘上的文件格式也不同。

Innodb：frm是表定义文件，ibd是数据文件
Myisam：frm是表定义文件，myd是数据文件，myi是索引文件。

Myisam

Myisam 的数据文件和索引文件是分开的，所以通过索引搜索到数据后需要在从数据文件中读取数据。（非聚集索引）

InnoDB

InnoDB索引实现(聚集索引),表数据文件本身就是按B+Tree组织的一个索引结构文件，聚集索引-叶节点包含了完整的数据记录。

1. 主键索引: 数据直接挂在叶子结点上。
   
2. 非主键索引 :叶子节点存储的是主键值,可能需要回表操作。（若使用到覆盖索引则不需要回表）。
   

联合索引（多列索引）

联合索引是指对表上的多个列进行索引，联合索引也是一棵B+树，不同的是联合索引的键值数量不是1，而是大于等于2,按索引列顺序 建立b+树.如下图以name、age、position三个字段建立索引:

最左匹配原则（左列匹配原则）

数据存储的结构是有序的（B+树） 所以需要按照索引建立的顺序进行数据搜索才能使用到索引结构。

常见问题

1. 为什么通常innoDB 表都推荐要建一个主键 ，并推荐使用整型的自增主键?

   建立主键?

   底层数据结构为B+树 需要一个不重复的列来构建树结构，如果没有设置主键 mysql会选择一个不重复的列进行树构建 若没有符合条件的列则会简历一个隐藏列

   整型主键?

   数据检索的过程实际的是数据值的大小进行比较 字符串大小比较需要从第一个字符开始比较,整型占有空间也更小 所以推荐整型主键

   自增主键?

   提高树的插入性能

2. 聚集索引和非聚集索引查找数据哪个更快?

   聚集索引快 因为数据和索引在同一个文件中可以直接获取?

3. innoDB为什么非主键索引结构叶子结点上存储的是主键而不是所有数据?

   数据一致性和节省存储空间。

4. 索引实现导致全表扫描出现的情况(以B+树的特性出发进行分析)

• in、not in : 可能会出现多次树检索 多次回表操作 mysql会认为直接进行全表扫描更快.
• 字段类型不一致:字段类型不一致可能会触发数据库函数进行类型转换,此时b+树的顺序就不能用于检索了。 注意⚠️:数值字符串类型主键用 数值搜索会导致索引失效 但是数值主键用字符串搜索不会失效