MySQL为什么选择B+树存储索引

为什么加索引?

如果上面的表,我们执行SQL语句

select * from table where Col2=89;

这样就会造成全表扫描，从第一行读取到倒数第二行，然后拿到这个89这个对应的值的位置，这样就做了6次才找到对应的值，但是加上索引就不一样了，接下来介绍索引是什么?

MySQL的索引是什么

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

索引的数据结构包括：

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

索引存储方式

索引存储是按照KV方式进行存储的，key是这个索引元素，比如34，77等，value是这个索引在磁盘上面的文件地址，索引也是落地到磁盘上面的，因为数据是落在磁盘上面的，然后根据这个key对应的value去磁盘上面找到对应的值，然后输出。

数据使用索引的存储方式

这样是不是就很快了

但是二叉树这个数据结构在某些情况下并没有什么效果，比如这个col1这一列，他是1-6的连续数据。

他的二叉树结构就是如下

虽然还是二叉树，但是这个和没有索引效果是一样的

所以MySQL最终选的不是二叉树然后第一种二叉树排除了然后对比一下红黑树

jdk1.8之后hashmap之前就是数组加链表存储的，假如链表非常长的时候，在hashmap里面查找元素性能也不是很好的快速查找所以在jdk1.8之后，在hashmap的底层链表被优化成红黑树，查找性能优化很高

红黑树的索引要是将1-7变成如下

红黑树也是二叉树，也叫做自平衡二叉树，二叉平衡树

但是MySQL最后之所以没有选择红黑树，因为红黑树在某些场景下并不能满足需求，因为用红黑树存储索引在某些情况下有如下问题：

• 层级太多，因为我们只有7个数据，层数即高度就这么多，如果要是很多的数据，那样不就更多了，假如树的高度是20，我们查找的元素在叶子结点,最快最快也要经过20次查找，也就要经过20次磁盘io查找。
• MySQL是将这个数据结构存储在磁盘上面的，假如你先存储了10个数据，然后过了几天又存储了10个数据，中间间隔了很多天，因为数据都是要写到磁道上面，这段时间间隔可能写了很多其他数据，可能都跨磁道了，这样查询起来更慢了，因为他也是都磁盘上面找的。

树的高度越低，查找速度越快，最好对这个树的高度做一下优化，即使上千万数据，也让这个树的高度小于4，这个是可能的。

因为我们比如插入一条数据，他是先在磁盘上面开辟一个空间，然后再将数据存储上去，我们就可以一次开辟多个空间，这一行存储多个节点，然后这个多个节点又能分出很多只。

上图就得到了一个B树的结构,

所以就引出了B树，B树就是B-树，两个是一个东西

他就是上面二叉树的变种，只不过每一个节点存储了多了key和value，而不是之前的一个

MySQL底层实际上用的是B树的变种，叫B+树

B+树他的叶子节点才会存储这个data，这个data对应的是这个数值在磁盘上面存储的位置，即我们最上面说的那个value

B+树每一个节点从左往右是依次递增的，而且15、18是在15-20之间，叶子结点之间用指针链接。

子节点大于等于他左边的父节点，小于右边的父节点

所有叶子结点也是从左往右依次递增，MySQL维护时候也是方便维护的

B+树也叫多路(叉)二叉树，底层也是二叉树

MySQL在B+树下如何查询：

查找30为例

1. 首先将最上面的这个如15、56、77加载到内存，这是一次磁盘的IO操作，然后在内存查找
2. 然后发现30是位于15、56之间，然后去他们两个之间的那个空白节点把下面第二行的地址拿到，然后将这个对应的第二行加载到内存，又是一次磁盘IO操作
3. 然后发现这个30位于20和49之间，然后读这个第二行的20和49之间的地址，将对应的第三行读取到内存，第三次磁盘IO。

疑问：为什么不把所有数据都放在第一行呢？

答：假如数据量很大，几千万行数据，一次把几千万行数据直接加载到内存，那样内存大概率感触几百兆。而且一次磁盘IO撑死几M，可能就几十K，几百兆的一次磁盘IO完成不了，磁盘IO几百兆也需要几秒钟或者几十秒。

所以这个每一行每一点存储多少K的数据，MySQL给我们提供了一个默认的，16K，这个一次磁盘IO读取16K数据还是很简单的，这个值是MYSQL研发人员在多次测试的成果下给设置的默认值，单位是byte

SHOW GLOBAL STATUS LIKE 'Innodb_page_size';

为什么MYSQL默认设置为16K?

一般索引都是用 INT 或 BIGINT

以bigint为例，比如这个索引15一般MySQL给他存储的是8B，然后他和56之间的空白格，这个是下一排的地址。是一个指针，索引和指针成对出现，这个一般是存储6B，MySQL给的值，所以一行16K*1024/(8+6)=1170个

叶子节点是没有这个空白区域，因为空白区域存放的是指针，叶子节点不需要指向下一位，所以没有这个指针，他的data占用的比较大，大概是1KB左右，所以叶子节点一个是存储16个元素

假如一个三层的B+树放满了,就是1170 1170 16≈两千两百万

所以就可能千万级别数据只需要查询三层

hash表存储方式

MySQL的索引也可以按照hash表存储方式

MyISAM和InnoDB存储引擎：只支持BTREE索引， 也就是说默认使用BTREE，不能够更换

但是hash索引某些存储引擎比如innodb是不支持的，除非经过特殊设置

hash表索引在MySQL用的很少

虽然用navicat在innodb和mylsam引擎下，可以选择hash索引，但是你会发现,点击保存，自动变成了BTREE，如果是memory引擎，他就可以选择hash索引，memory存储引擎支持hash索引存储和BTREE方式

如果使用hash表存储的话，就是hash(索引值)，把这个hash索引值之后的结果和磁盘地址两个做一个唯一的映射，这样看起来好像感觉执行比如下面这个SQL好像比B+TREE更快，因为只需要对这个索引做一次hash，然后拿这个这个hash值去磁盘映射的位置找到这个对应的值即可

另外MySQL底层对hash碰撞(如果两个输入串的hash函数的值一样，则称这两个串是一个碰撞)规避得很好

select * from a where Col1=1

但是，假如执行的是 select * from a where Col2<89 and Col2>34 ，这个就是B+TREE更快了，绝大部分场景都是范围查找吧。所以MySQL默认是B+tree，但是也可以选择hashTree

用B+树查找时候，实现范围查找就非常快了，他的叶子节点之间用指针连接起来的，而且是双向的，首尾相连的

而B树叶子结点没有指针的

假如查找的是10-50之间数据，找到20之后，又要从根节点索引元素查找到49，不能像B+树那样直接向右取

联合索引

这个就是把之前的一个字段转换成现在的三个字段而已，这个对比排序方式是首先按照第一个字段对比，都一样在比较第二个字段，在一样的话再比较第三个字段

原文链接：https://blog.csdn.net/Gan_1314/article/details/125783239?utm_source=tuicool&utm_medium=referral