推广

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

iseeyu3年前 (2024-02-21)推广123

image.png

如果上面的表,我们执行SQL语句
select * from table where Col2=89;
这样就会造成全表扫描,从第一行读取到倒数第二行,然后拿到这个89这个对应的值的位置,这样就做了6次才找到对应的值,但是加上索引就不一样了,接下来介绍索引是什么?

MySQL的索引是什么:

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

二叉树
红黑树
Hash表
B-Tree

索引存储方式

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

数据使用索引的存储方式

Col2二叉树存储方式

这样是不是就很快了

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

image.png

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

所以MySQL最终选的不是二叉树
然后第一种二叉树排除了.
然后对比一下红黑树
jdk1.8之后hashmap之前就是数组加链表存储的,假如链表非常长的时候,在hashmap里面查找元素性能也不是很好的快速查找所以在jdk1.8之后,在hashmap的底层链表被优化成红黑树,查找性能优化很高

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

image.png

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

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

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

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

image.png

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

B树解释:

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

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

image.png

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研发人员在多次测试的成果下给设置的默认值,单位是B
show global status like ‘Innodb_page_size’

image.png

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

image.png

假如一个三层的B+树放满了,就是1170117016=两千两百万
所以就可能千万级别数据只需要查询三层

hash表存储方式

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

image.png

MyISAM和InnoDB存储引擎：只支持BTREE索引，也就是说默认使用BTREE，不能够更换,
但是hash索引某些存储引擎比如innodb是不支持的,除非经过特殊设置
hash表索引在MySQL用的很少
虽然用navicat在innodb和mylsam引擎下,可以选择hash索引,但是你会发现,点击保存,自动变成了Btree,如果是memory引擎,他就可以选择hash索引,memory存储引擎支持hash索引存储和btree方式

image.png

如果使用hash表存储的话,就是hash(索引值),把这个hash索引值之后的结果和磁盘地址两个做一个唯一的映射,这样看起来好像感觉执行比如下面这个SQL好像比B+更快,因为只需要对这个索引做一次hash,然后拿这个这个hash值去磁盘映射的位置找到这个对应的值即可
另外MySQL底层对hash碰撞(如果两个输入串的hash函数的值一样，则称这两个串是一个碰撞)规避得很好
比如select * from a where Col1=1

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

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