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

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

  • 为什么加索引?
  • MySQL的索引是什么
  • 索引存储方式
  • 数据使用索引的存储方式
    • 二叉树
    • B树
    • hash表存储方式
  • 联合索引

为什么加索引?

MySQL为什么选择B+树存储索引_第1张图片

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

select * from table where Col2=89;

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

MySQL的索引是什么

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

索引的数据结构包括:

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

索引存储方式

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

数据使用索引的存储方式

二叉树

MySQL为什么选择B+树存储索引_第2张图片

这样是不是就很快了

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

他的二叉树结构就是如下

MySQL为什么选择B+树存储索引_第3张图片

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

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

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

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

MySQL为什么选择B+树存储索引_第4张图片

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

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

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

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

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

MySQL为什么选择B+树存储索引_第5张图片

上图就得到了一个B树的结构,
所以就引出了B树,B树就是B-树,两个是一个东西

B树

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

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

MySQL为什么选择B+树存储索引_第6张图片

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为什么选择B+树存储索引_第7张图片

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

一般索引都是用INTBIGINT

以bigint为例,比如这个索引15一般MySQL给他存储的是8B,然后他和56之间的空白格,这个是下一排的地址。是一个指针,索引和指针成对出现,这个一般是存储6B,MySQL给的值,所以一行16K*1024/(8+6)=1170个
叶子节点是没有这个空白区域,因为空白区域存放的是指针,叶子节点不需要指向下一位,所以没有这个指针,他的data占用的比较大,大概是1KB左右,所以叶子节点一个是存储16个元素

MySQL为什么选择B+树存储索引_第8张图片

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

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

hash表存储方式

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

在这里插入图片描述

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

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

hash表索引在MySQL用的很少

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

MySQL为什么选择B+树存储索引_第9张图片

如果使用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+树查找时候,实现范围查找就非常快了,他的叶子节点之间用指针连接起来的,而且是双向的,首尾相连的

MySQL为什么选择B+树存储索引_第10张图片

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

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

MySQL为什么选择B+树存储索引_第11张图片

联合索引

MySQL为什么选择B+树存储索引_第12张图片

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

原文

你可能感兴趣的