探究Mysql索引底层的bmore树的非叶子节点数据为什么小于4kb

  1. 云栖社区>
  2. 博客>
  3. 正文

探究Mysql索引底层的bmore树的非叶子节点数据为什么小于4kb

it乾坤 2019-08-20 18:37:10 浏览120
展开阅读全文

为什么要设置B+树的非叶子节点数据小于4kb呢,我们往下一探究竟

原因如下所示

因为数据库里面的索引就是使用的bmore树,所以我们使用sql语句来讲解bmore树的产生:

比如有下面的两个常用的需求:

根据某个值查找数据,比如select * from user where id=1234;
根据区间值来查找某些数据,比如select * from user where id > 1234 and id < 2345。

为了让二叉查找树支持按照区间来查找数据,我们可以对它进行这样的改造:树中的节点并不存储数据本身,而是只是作为索引。除此之外,我们把每个叶子节点串在一条链表上,链表中的数据是从小到大有序的。就像下面这样:

2019073009030515

改造之后,如果我们要求某个区间的数据。我们只需要拿区间的起始值,在树中进行查找,当查找到某个叶子节点之后,我们再顺着链表往后遍历,直到链表中的结点数据值大于区间的终止值为止。所有遍历到的数据,就是符合区间值的所有数据。

20190730090334667

但是,我们要为几千万、上亿的数据构建索引,如果将索引存储在内存中,尽管内存访问的速度非常快,查询的效率非常高,但是,占用的内存会非常多。
比如,我们给一亿个数据构建二叉查找树索引,那索引中会包含大约1亿个节点,每个节点假设占用16个字节,那就需要大约1GB的内存空间。给一张表建立索引,我们需要1GB的内存空间。如果我们要给10张表建立索引,那对内存的需求是无法满足的。如何解决这个索引占用太多内存的问题呢?

我们可以借助时间换空间的思路,把索引存储在硬盘中,而非内存中。我们都知道,硬盘是一个非常慢速的存储设备。通常内存的访问速度是纳秒级别的,而磁盘访问的速度是毫秒级别的。读取同样大小的数据,从磁盘中读取花费的时间,是从内存中读取所花费时间的上万倍,甚至几十万倍。所以我们通过减少访问磁盘索引的次数来减少这个访问磁盘的查询速度。怎么减少呢,就是让每个节点的读取(或者访问),都对应一次磁盘IO操作,这样树的高度就等于每次查询数据时磁盘IO操作的次数。

所以我们要把bmore树创建成m叉树,因为m值越大,树的高度也就越低,如图所示,给16个数据构建二叉树索引,树的高度是4,查找一个数据,就需要4个磁盘IO操作(如果根节点存储在内存中,其他结点存储在磁盘中),

20190730090354476

如果对16个数据构建五叉树索引,那树的高度只有2,查找一个数据,对应只需要2次磁盘操作。如下图所示

20190730090417259

如果m叉树中的m是100,那对一亿个数据构建索引,树的高度也只是3,最多只要3次磁盘IO就能获取到数据。磁盘IO变少了,查找数据的效率也就提高了。

但是m值也不是越大越好,因为不管是内存中的数据,还是磁盘中的数据,操作系统都是按页(一页大小通常是4KB,这个值可以通过getconfig PAGE_SIZE命令查看)来读取的,一次只会读一页的数据。如果要读取的数据量超过一页的大小,就会触发多次IO操作。所以,我们在选择m大小的时候,要尽量让每个节点的大小等于一个页的大小。读取一个节点,只需要一次磁盘IO操作。

那么什么叫做一个节点的大小呢,比如下面的数据,下面的篮筐的这个节点,它里面存储的数据,就是可以存储所有子节点里面的数据,但是不包含本节点的数据,本节点的数据在本节点的父节点里面存储着。什么意思呢,看下面的图片,下面的蓝框里面的30,65其实是在下面的蓝框的父节点红框节点里面存储着,然后下面的绿色框里面的30,65其实是在父节点蓝框节点里面存储着,同时蓝框节点还存储着下面的绿色框里面的所有字节点数据,所以只要保证红框节点,蓝框节点等节点的数据大小不超过4kb就可以了,那么如果超过了怎么办呢,超过4kb大小的节点都会被mysql处理掉,这里就要去看bmore树的添加和删除了

20190730090438908

能看到这里的同学,就帮忙点个赞吧,Thanks(・ω・)ノ

网友评论

登录后评论
0/500
评论
it乾坤
+ 关注