如何理解数据库的B+树

本文介绍了“如何理解数据库的B树”的知识。很多人在实际案例的操作中会遇到这样的困难。让边肖带领你学习如何处理这些情况。希望大家认真阅读，学点东西！

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

我们通常会接触到机械硬盘和固态硬盘。存储器是一种半导体器件。对于内存，当我们知道内存地址时，就可以通过地址获取数据，这是内存的随机存取特性。访问速度快但成本高，所以内存空间一般很小。

对于磁盘，它们是机械设备。每当磁盘访问数据时，都需要等待磁盘旋转到磁头，才能读取相应的数据。即使磁盘转得很快，与内存的随机存取相比，仍然是渣。可以看出，如果是随机读写，其性能差距非常大。如果是按顺序访问大量数据的时候，磁盘和内存的性能差距其实很小。为什么呢？

磁盘的最小读/写单位是扇区。现在磁盘扇区一般是4k字节。对于操作系统，一次将读取多个扇区。到目前为止，操作系统的最小读取单位是块。每当我们从磁盘读取一段数据时，操作系统会一次读取整个数据块，所以对于大量的顺序读写，磁盘效率会比随机读写高很多。

现在，假设您有一个有序数组，所有数组都存储在磁盘上的块中。现在，我们找到了二分搜索法的元素A。首先，我们找到中间元素，把它从块中取出，从磁盘放入内存，然后在内存中做二分搜索法。在下一步中，如果搜索到的元素在其他块中，我们需要继续从磁盘读取内存。反复从磁盘到内存，效率会很低。因此，我们需要找到一种方法，使磁盘的访问次数尽可能低。

2 数据和索引分离

我们以公安系统为例。系统中用户众多，每个用户除了姓名、年龄等基本信息外，还有唯一的ID。当我们得到这个ID，就可以知道相应的基本信息。但是，每个用户的基本信息太多，无法存储在内存中，所以应该存储在磁盘中。

用户数据

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

有序数组

然而，在数据频繁变化的场景下，有序数组的弊端就显现出来了。在大多数情况下，我们仍然考虑使用二叉查找树或哈希表。但是，哈希表不支持区间查询，因此更经常使用二分搜索法树。如下图所示

在此插入图片描述。

如果索引太多，不能完全存储在内存中，可以考虑将索引存储在磁盘中吗？如何高效地组织磁盘中的索引结构？这就引入了B树。

2 B+树

使节点大小等于块大小。

我们知道，当操作系统访问磁盘时，它通常以块的形式读取磁盘。如果你目前只需要读取几个字节的数据，但磁盘还是会读出整个块，读写会不会效率低？在B-tree中，大榭使节点的大小等于块的大小，并在节点中存储有序数组而不是元素，从而充分利用操作系统的例程，最大化读取效率。

内部节点和叶节点。

虽然内部节点和叶节点具有相同的结构，但是它们存储的内容不同。内部节点存储键和维护树结构的指针，但不存储与键对应的数据。叶节点存储密钥和相应的数据，但不存储指针来维护树结构，这最大化了节点空间的利用率。

内部节点和叶节点。

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+树”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站，小编将为大家输出更多高质量的实用文章！