MySQL数据库索引详解

2022-10-14 22:55:15

目标
索引的本质
MYISAM存储引擎
InnoDB存储引擎
联合索引
最左前缀原则

目标

1、索引数据红黑树、Hash、B+树详解
2、千万级数据表如何用索引快速查找
3、如何基于索引B+树准确建立高性能索引
4、联合索引底层数据结构是怎样的
5、聚集索引与覆盖索引
6、Mysql的最左前缀原则
7、为什么推荐使用自增主键做索引
8、Mysql索引优化规则

索引的本质

按照官方的定义，索引就是按用户任意指定的字段对数据进行排序的一种数据结构。

使用InnoDB存储引擎时，在插入数据的时候，会自动把字段排好序（聚集）；
而用MYISAM存储引擎时，默认按插入数据的顺序进行存储，不会排序（堆表）。

索引的数据结构

二叉树
红黑树
Hash表
B-Tree

假如现在有一个2列7行的表，如下图：

上图左边的： 0x07、0x56 这些表示的是数据在磁盘上存储的首地址指针。

按照不同的数据结构生成的索引也是不同的，比如：

下面是以 COL2 字段建的索引：

二叉树

二叉树的特点就是：它右边的子元素是大于等于它的父元素，而左边的子元素是小于它的父元素的。

缺点：如果是插入了有小到大一次递增的索引是，数据结构就变成了链表了。结果就是建了索引跟没建一样，走的就是全表扫描。

红黑树

红黑树的本质是一个二叉平衡树，当树一边链表太长的时候，它会自动平衡。

缺点：树的高度太高，查找的次数多。

Hash表
hash算法算出字段的hash值，然后把hash值跟磁盘数据列地址指针做高速映射。
hash在等值查找的时候，性能是非常不错，但是在范围查找的时候效率就不行了。因为还是得挨个遍历出来。
B Tree
- 页子节点具有相同的深度，页节点的指针为空
- 所有索引元素不重复
- 节点中的数据索引从左到右递增排列

缺点：没有双向指针，范围查找的时候不如b+树。而且，b树的叶子节点存储了data，这样整个树在高度h<=3时存储的索引少了很多。

B+Tree
- 非页子节点不存储数据（data），只存储索引（冗余），可以放更多的索引。
- 页子节点包含所有索引字段。
- 页子节点用指针连接，提高区间访问性能。

现在来看一下B+树，可以存放多少索引元素：

mysql中存储数据的单位是页，跟操作系统类似，只不过操作系统中的大小为4kb，而mysql的页的大小是16kb。

假设图中的索引是一个bigint类型的主键索引，bigint类型占8位，也就是说一个索引数据是8b，而图中的空白元素实际上是指下一个子节点的磁盘文件地址，默认占6b。这样计算一下： 16kb/(8+6) = 1170。也就是说一个页大概可存储1170个索引。这是树第一层非叶子节点，可以存这么多。第二层也是非叶子节点，同理可算： 1170 x 1170 = 1368900。可以存储1368900个索引。第三层则是页子节点，它没有下一层，但是每一个索引下面会有一个data，这个data有可能是索引所在行的磁盘文件地址，有可能是索引所在行的其他列的数据。这个不同的存储引擎，放的东西是不一样的。现在假设这个data里放的是索引所在行的其他字段信息，这样它占的空间比较大，所以假设索引+data为1kb的大小，这样，每个页就有16个索引，所以总共可以放：1170x 1170 x 16 = 21902400 个索引。这个数量级完全够我们用的，所以mysql采用B+树这种数据结构来存储索引。

B+树的根节点是放在内存的，索引在sql查询的时候，如果树的高度h=3，最多也只会进行2次磁盘IO。

MYISAM存储引擎

MYISAM索引文件和数据文件是分离的。（非聚集）

查看mysql文件存储位置：

show global variables like "%datadir%";

MYISAM存储引擎，在磁盘上对应有3个文件： xx.frm、xx.MYD、xx.MYI 文件，没有截图就不放了。

下面看看对应的逻辑图：

假设Col1是索引字段，那么图中，上部分B+树结构数据就是放在 xx.MYI 文件里，而下面的表一条一条数据就是放在 xx.MYD 文件中的。

InnoDB存储引擎

InnoDB索引文件和数据是在一起的，存在于一个文件中。（聚集）

表数据文件本身就是按照B+树组织的一个索引结构文件
聚集索引叶子节点包含了完整的数据记录
为什么InnoDB表必须要有主键，并且推荐整形自增主键
- 答：①、InnoDB规定是按照主键索引把数据组织起来的，如果没有显式定义主键的话，mysql会默认查找表中的字段，看有没有唯一性的字段。如果有，那么就把它作为主键。如果没有唯一性的字段，那么mysql会隐式的创建一个字段（rowId）自增的整形，来作为主键索引。
- 答：②、1、使用整形的自增，很简单如果不是整形的话，比如说UUID，那么UUID这种字符串进行比较（ASCII码）大小，肯定没有整形的数据（1<2）这种效率高。2、而且使用整形比UUID更省空间。3、自增的话就保证每次插入数据都在后面插入，因为b+树要求叶子节点的数据要从左到右一次递增的。（不自增的话，可能插入的数据在前面，会导致叶子节点分裂，然后做一次平衡，性能和效率会降低）
为什么非主键索引结构叶子节点存储的是主键值（一致性和节省存储空间）