如何理解数据库的B+树

本篇内容介绍了“如何理解数据库的B+树”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

创新互联公司是一家以网站建设公司、网页设计、品牌设计、软件运维、seo优化、小程序App开发等移动开发为一体互联网公司。已累计为木托盘等众行业中小客户提供优质的互联网建站和软件开发服务。

1 数据从磁盘读写与内存读写有哪些不同

我们平时接触的有机械硬盘和固态硬盘。内存属于半导体器件，对于内存，我们知道内存地址就可以通过地址拿到数据，也就是内存的随机访问特性。访问速度快但是贵，所以内存空间一般比较小。

对于磁盘，属于机械器件。每当磁盘访问数据的时候，都需要等磁盘盘片旋转到磁头，才能读取相应的数据，即使磁盘的转速很快，但是和内存的随机访问相比还是渣渣。所见，如果是随机读写，其性能差距是非常大的。那如果是顺序访问大量数据的时候，磁盘的性能和内存其实差距就不大了，这是为啥?

磁盘的最小读写单位是扇区，现在磁盘扇区一般是4k个字节，对于操作系统，一次性会读取多个扇区，至此操作系统的最小读取单位就是块。每当我们从磁盘读取一个数据，操作系统就会一次性读取整个块，那么对于大量的顺序读写来说，磁盘效率会比随机读写高很多。

假设现在你有个有序数组，全部以块的方式存放在磁盘中，现在我们通过二分查找的方式查找元素A。首先我们找到中间元素，并从块中取出，将其从磁盘放入内存中，然后再内存中进行二分查找。在进行下一步的时候，如果查找的元素在其他块中，我们需要继续从磁盘读出到内存中。这样反反复复的从磁盘到内存，其效率将非常的低。所以我们需要想办法让访问磁盘的次数尽可能的低。

2 数据和索引分离

我们以公安系统为例。系统中的用户非常多，每个用户除了姓名，年龄等基本信息外，当然还有一个唯一标识的ID，我们拿到这个ID，就可以知道对应的基本信息。但是每个用户的基本信息太多不可能全部存放在内存中，因此考虑存储于磁盘中。

用户数据

采用有序数组的方式，其中分别存储用户ID和用户信息所在磁盘的位置，这样我只需要存放两个元素，直接存放于内存。如下图所示

有序数组

但是在数据频繁变化的场景中，有序数组的弊端就出现了。大部分情况还是考虑使用二叉检索树或者哈希表的方式。但是哈希表又不支持区间查询，因此更多的使用二叉检索树的方式。如下图所示

在这里插入图片描述

如果索引太多，依然不能完全存放于内存中，那我们是不是可以考虑将索引也存放于磁盘中?如何高效的在磁盘中组织索引的结构?这就引入了B+树

2 B+树

• 让节点大小等于块大小

我们知道操作系统在对磁盘进行访问的时候，通常是按照块的方式读取。如果当前你需要读取的数据只有几个字节，但是磁盘依然会将整个块读出来，这样子是不是读写效率就很低呢。在B+树中，大佬采用让一个节点大小等于一个块的大小，节点中存放的不是一个元素，而是一个有序的数组，这样充分利用操作系统的套路，使得读取效率的最大化

• 内部节点与叶子节点

内部节点和叶子节点虽然是一样的结构，但是其存储的内容有所区别。内部节点存放key以及维持树形结构的指针，它并不存放key对应的数据。而叶子节点存放key和对应的数据，不存放维持树形结构的指针，这样使得节点空间的利用最大化。

内部节点与叶子节点

• B+树使用双向链表的方式，具有良好的范围查询能力和灵活的调整能力

综上三点，B+树是一颗完全平衡的m阶多叉树。

m阶多叉树

3 B+树的检索方案

刚才吹了一波B+树多么的牛逼，到底是怎么检索的?具体的查找过程是这样的：我们先确认要寻找的查询值，位于数组中哪两个相邻元素中间，然后我们将第一个元素对应的指针读出，获得下一个  block 的位置。读出下一个 block 的节点数据后，我们再对它进行同样处理。这样，B+  树会逐层访问内部节点，直到读出叶子节点。对于叶子节点中的数组，直接使用二分查找算法，我们就可以判断查找的元素是否存在。如果存在，我们就可以得到该查询值对应的存储数据。如果这个数据是详细信息的位置指针，那我们还需要再访问磁盘一次，将详细信息读出

B+树是一个m阶的多叉树，所以B+树中的一个节点可以存放m个元素的数组，ok，这样的话，只需要几层的b+树就可以索引数据量很大的数了。比如1个2k的节点可以存放200个元素，那么一个4层的B+树就能存放200^4，即16亿个元素。

如果只有四层，意味着我们最多访问磁盘4次，假设目前每个节点为2k，那么第一层就一个节点也就2k，第二层节点最多200个元素，一共就是0.8M。第三层200^2，也就是40000个节点，一共80M。对于当前的计算机而言，我们完全可以将前面三层存放于内存中，只需要将第四层存放于磁盘中，这样我们只需要和磁盘打一次交道就分手，也就是面试想知道的为什么要分为内部节点与叶子节点。

4 B+树如何进行动态的调整

上面介绍了B+树的结构和查询原理，现在我们看看B+树增加和删除是怎么个情况

现在我们以三个元素的B+树 为例，假设目前我们要插入ID为6=5的元素，第一步先查找对应的叶子节点，如果叶子节点没有满，直接插入即可

插入元素6

如果我们插入的元素是10?按道理我们应该插入到9后面，但是节点已经满了，所以我们需要采取其他的方式。方法是将此叶子节点进行分裂，即生成一个新的节点，然后将数据在两个节点中平分。

节点分裂

很明显，叶子节点的分裂影响到了父节点，如果父节点也是满的，也要进行分裂

节点分裂

“如何理解数据库的B+树”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站，小编将为大家输出更多高质量的实用文章！