第一篇：MySQL索引数据结构演进之你心里有B树（数）吗

什么是索引

在关系数据库中&＃xff0c;索引是一种对数据库表中一列或多列的值进行排序的一种存储结构&＃xff08;数据结构&＃xff09;&＃xff0c;索引解决的问题是查询速度慢。容易产生理解偏差的点解释一下&＃xff1a;

• 索引是针对表来说的&＃xff0c;不是针对数据库来说的&＃xff08;建表的sql语句中的index就是索引&＃xff09;。
• InnoDB存储引擎不是MySQL自己的&＃xff0c;而是Innobase Oy公司开发的&＃xff0c;该公司后被甲骨文公司并购

索引的数据结构演进

链表结构

假设用户表中有字段id&＃xff0c;name&＃xff0c;password。我们需要对这个表进行查询。

我们知道数据都是存储在容器中的&＃xff0c;假设现在上表中的数据存放在一个链表中&＃xff0c;执行以下SQL可以发现影响查询速度的是这条数据在第几行。

select * from user where password &＃61; 33 ; //查找1次
select * from user where password &＃61; 36 ; //查找2次
select * from user where password &＃61; 1 ; //查找3次
select * from user where password &＃61; 26 ; //查找4次
select * from user where password &＃61; 9 ; //查找5次
select * from user where password &＃61; 47 ; //查找6次
select * from user where password &＃61; 5 ; //查找7次
select * from user where password &＃61; 99 ; //查找8次
select * from user where password &＃61; 52 ; //查找9次


假设表中有1000万条数据&＃xff0c;现在要查询第1000万条数据&＃xff0c;这样就需要查找1000万次。顺序查找的问题是存储数据的结构是线性的&＃xff0c;也就是说想要查询第2条数据&＃xff0c;我需要知道第1条数据是什么。大家可能会考虑到为什么不要数组&＃xff0c;直接通过下标就可以查到数据&＃xff0c;问题是数组是固定长度的&＃xff0c;那么数组长度定义为多少合适呢&＃xff1f;

二叉树

要解决链表问题&＃xff0c;我们可以使用树来解决&＃xff0c;先来看下二叉树&＃xff0c;二叉树与链表的区别是链表就一条搜索路径&＃xff0c;二叉树有两条搜索路径。上表中对应的二叉树如下。

与链表一样&＃xff0c;我们看看查询需要的次数&＃xff0c;可以看出&＃xff1a;二叉搜索树通过增加了一条搜索路径&＃xff0c;提高了查询效率&＃xff0c;查找的效率取决于树的深度&＃xff08;高度&＃xff09;。

select * from user where password &＃61; 33 ; //查找1次
select * from user where password &＃61; 36 ; //查找2次
select * from user where password &＃61; 1 ; //查找2次
select * from user where password &＃61; 26 ; //查找3次
select * from user where password &＃61; 9 ; //查找4次
select * from user where password &＃61; 47 ; //查找3次
select * from user where password &＃61; 5 ; //查找5次
select * from user where password &＃61; 99 ; //查找4次
select * from user where password &＃61; 52 ; //查找5次


假设有1~9个数字要存储在二叉树中。由于二叉树的特点是&＃xff0c;任一节点的左子节点都小于父节点&＃xff0c;右子节点都大于父节点。当插入的数据是单向递增或递减时&＃xff0c;二叉树就会变成线性结构&＃xff0c;查询效率与链表就一致了。

红黑树

为了解决二叉树变链表的问题&＃xff0c;出现了红黑树。红黑树会做一个平衡。平衡后树的高度就变成了4层&＃xff0c;相比于二叉树&＃xff0c;效率更高。
但是红黑树依然存在瓶颈&＃xff0c;以1000万条数据为例&＃xff08;树的高度大概是24&＃xff09;&＃xff0c;最坏的情况需要查找24次&＃xff01;查找24次是概念呢&＃xff1f;&＃xff0c;MySQL存储数据是存文件的&＃xff0c;每次查找都需要读一次文件到内存&＃xff0c;即最坏的查询情况需要读24次文件到内存&＃xff0c;也就是24次IO操作&＃xff0c;这是非常耗时的。

B树

因为树的高度问题&＃xff0c;出现了B树&＃xff08;多路查找平衡树&＃xff09;&＃xff0c;B树的思路是多叉树。只要分叉越多&＃xff0c;那么每一层可以存放的元素就越多&＃xff0c;树的层级自然而然就会降低。那么分叉肯定是越多越好&＃xff0c;最多可以多到什么程度呢&＃xff1f;这取决于MySQL一页可存储的数据量是多少&＃xff0c;我们可以通过SQL命令来查询&＃xff1a;

可以看到MySQL默认一页是16384字节&＃xff0c;大约是16kb。假设一条数据1KB为例&＃xff0c;一颗高度为3的B树&＃xff0c;可以存储的数据个数是 16 * 16 * 16 &＃61; 4096

B&＃43;树

我们知道Innodb的索引数据结构是B&＃43;树。可以我们看到B&＃43;树跟B树好像没有什么太大的差距&＃xff0c;这里是数据量少的原因。B树效率高是因为分叉多&＃xff0c;每行的节点变多了。通过计算高度为3的B树只能存放4096条数据&＃xff0c;显然还待演进。

B树中的每个节点都包含指针和数据两部分&＃xff0c;数据所占据的位置是较大的&＃xff0c;我们是否可以考虑第一层第二层只存放指针&＃xff0c;将数据都放到第三层。这样单个叶子节点可以存放的指针数量是 1170&＃xff08;16 * 1024 /(8&＃43;6)&＃xff09;左右&＃xff0c;那么高度为3的B&＃43;树就可以存储1170117016个数据&＃xff08;假设索引使用的是bigint类型&＃xff08;java中占8个字节&＃xff09;&＃xff0c;6是一个指针需要的空间&＃xff09;

细心的小伙伴会发现实际B&＃43;树的叶子节点之间会有一个单向的箭头&＃xff0c;实际这里的箭头是双向的&＃xff0c;图不对。这个箭头代表的是前后叶子节点的存储位置。索引是排序后的数据结构&＃xff08;大家可以观察第二行就是有序的&＃xff09;。比如查询语句select * from table where num <5&＃xff1b;查询时直接取5左边的数据即可&＃xff0c;及大提高了效率。

可能有人会有这样的疑问&＃xff1a;**为什么不把所有的索引放第一层&＃xff0c;这样只要两层不就好了吗&＃xff1f;**原因如下

1. 如果第一层有几百M数据&＃xff0c;一次磁盘io也加载不了那么多数据
2. ram中使用是折半查找&＃xff0c;几千万数据也不会很快

哈希

我们一般讲索引都是B&＃43;树&＃xff0c;实际MySQL中还有一种选择是hash。在查询时where后的条件是等值查询&＃xff08;&＃61;或in&＃xff09;下&＃xff0c;hash的速度比B&＃43;树是要快的。B&＃43;树有3层&＃xff0c;哈希只需要计算一次即可。

既然哈希效率这么快&＃xff0c;为什么没有人使用呢&＃xff1f;主要有两个原因&＃xff1a;

1. 使用场景少&＃xff0c;实际场景范围查询更多
2. 哈希会有哈希冲突

最左前缀原理

最左前缀原理就是当表设置了组合索引&＃xff0c;那么必须满足最左边字段在前的规定&＃xff0c;下面通过实际案例来看。

可以这么思考&＃xff1a;索引这么好&＃xff0c;为什么不每个字段都加个索引&＃xff1f;实际加索引就会生成一颗索引树。大量的索引树是非常占用存储空间的。所以实际场景中一般都是组合索引用的比较多一点。假设上表中创建了组合索引&＃xff08;name,password&＃xff09;。那么以下sql是否会走这个组合索引的SQL。

select * from user where name &＃61; ? and password &＃61; ? ;
select * from user where password &＃61; ? and name &＃61; ? ;
select * from user where name &＃61; ? ;


1. 第一个SQL会走索&＃xff1a;左边是name&＃xff0c;后面是password&＃xff0c;完美用上
2. 第二个SQL不走索引&＃xff1a;虽然两个字段都有&＃xff0c;但是name在后
3. 第三SQL会走索引&＃xff1a;组合索引只要满足组合中的第一个字段即可

聚集索引与非聚集索引

实际场景中&＃xff0c;表中虽然有些业务字段可以当做主键&＃xff0c;但是一般不这么做。一般都是添加一列作为数据的主键。这个主键也叫聚集索引&＃xff0c;是用来生成主键树的。innodb下这个主树上存有数据的&＃xff0c;回主树的过程就称为回表。

如果建表时没有设置主键&＃xff0c;那么数据库就尝试查找某个字段没有重复的&＃xff0c;用这个字段生成主树。如果没有这样的字段&＃xff0c;数据库会为我们生成一个rowid&＃xff08;隐藏列&＃xff09;&＃xff0c;使用隐藏列来生成主树。

学习时思考过的问题及答案

1. 为什么线性结构不用二分查找&＃xff1a;因为数据是读到内存里&＃xff0c;数据量大的情况下内存放不放的下是个问题
2. 红黑树&＃xff0c;二叉平衡树层级高。两千万数据大概32层&＃xff0c;32次IO是否能接收&＃xff1a;磁盘IO是非常耗时的操作&＃xff0c;是从文件中读数据到内存中
3. B树采用空间换时间&＃xff1a;将原来32层变成3层。增加了每次读到内存里数据的多少&＃xff0c;减少了树的高度&＃xff08;即减少了时间&＃xff09;
4. 辅助索引为什么不存所有数据&＃xff1f;存两份一样的数据没有意义&＃xff0c;还要考虑两棵树的数据同步问题
5. 回表会增加几次IO&＃xff1a;具体看主树的层级&＃xff0c;如果三层就是3次