MySQL-为什么使用b+树

Author Avatar
丁起男 01月 13,2021
  • 在其它设备中阅读本文章

MySQL-为什么使用b+树

磁盘io与预读

磁盘读取数据靠的是继续运动,每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三部分:

  • 寻道时间指的是磁臂移动到指定磁道所需要的时间,主流磁盘一般在5ms一下
  • 旋转延迟就是我们经常说的磁盘转速,比如一个磁盘7200/min,标识每分钟能转7200次,也就是说一秒能转120次,旋转延迟就是1/120/2 = 4.17ms,也就是半圈的时间(这里有两个时间:平均寻道时间,受限于目前的物理水平,大概是mms的时间,找到磁道了,还需要找到你数据存在的那个点,寻点时间,这寻点时间的一个平均值就是半圈的时间,这个半圈时间叫做平均延迟时间,那么平均延迟时间加上平均寻道时间就是你找到一个数据所消耗的平均时间,大概9ms,其实机械硬盘主要是慢在这个个时间上了,当找到数据然后把数据拷贝到内存的时间是非常短的);
  • 传输时间指的是从磁盘读出或将数据写入磁盘的时间,一般在零点几毫秒,相对于前两个可以忽略不计

那么访问一次磁盘的时间,即异常磁盘io的时间约等于9ms左右,听起来还挺不错的,但要知道一台500-MIPS的机器每秒可以执行5亿条指令,因为指令依靠的是电的性值,换句话说执行一次io的消耗时间cpu可以执行约450万条指令,数据库动辄十万百万甚至千万级数据,每次9毫秒的时间,显然是个灾难,所以要想办法降低io次数

考虑到磁盘io是非常高昂的操作,计算机操作系统做了一些优化,当一次io时,不光当前磁盘地址的数据,而是把相邻的数据也都读到内存缓冲区内,因为局部预读性原理告诉我们,当计算机访问一个地址的数据的时候,与其相邻的数据也会很快被访问到。每一次io读取的数据我们称之为页(page)。具体一页有多大数据根操作系统有关,一般为4k或8k也就是我们读取一页内的数据时,实际上才发生了一次io

为什么使用b+树而不是b树

  • 首先b+树的空间利用率更高(非叶节点没有data域),可减少io次数,磁盘读写所耗费的代价更低
  • b+树的查询效率更加稳定,b树搜索在非叶子还是叶子节点结束都有可能,越靠近根节点,查找效率越快;而b+树无论查找的是什么数据,最终都需要从根节点一直走向叶子节点,所有查找经过的次数都是一样的
  • b+树能同时支持随机检索和顺序检索,而b树只适合随机检索,顺序检索的效率比b+树低
  • 增删文件时,b+树的效率更高,因为所有的data都在叶子节点中,而b树删节点时还需要分裂,中间节点向上等操作

hash索引

hash索引更容易理解,底层就是hash表,调用一次hash函数就可以直接确定相应键值,之后进行回表查询实际数据,按理说hash索引比b+树还高效,为什么不使用hash索引呢?

  • hash索引不支持区间查找,类似select * from table where age>10这种查找
  • hash索引不支持模糊查询,像JoJoX和JoJoA之间没有关联性,原因在于hash函数的不可预测
  • hash索引在等值查询上很快,但是却不稳定,某个键值大量重复时,效率变得极差

原文:https://mp.weixin.qq.com/s/VUYse9nc8kq2qr_nIlwglQ