B/B+树(一) 从存储系统中的索引引入B树

一.何为索引

在正式介绍B树之前，我们先来了解一下什么是索引，这样我们才能心里更有b树！使用计算机无非就是基于计算机中的数据来使用，随着科技的发展，计算机中存储的数据不断增加，程序的计算离不开对数据的加载，而加载数据的前提是找到目标的数据。而如何快速找到目标数据，就是核心的问题。我们都知道一本书籍或者一本词典，都会带一个目录在前面，并且这个目录都是按照章节编号顺序或者小说进展的顺序排好，方便我们的查找。对于一个存储系统，我们同样也需要这样的目录，我们称之为索引，可以方便程序查询快速定位到想要的数据。

二.索引的数据结构

从上面的介绍我们可以看到，索引其实就是存储用户数据的位置的一种数据结构，或者说存储用于快速定位用户数据的一种数据结构。而我们使用这种数据结构主要的执行操作是查询和修改。查询很容易理解，也就是我们从索引中查询需要的数据的位置。修改也就是用户数据变化了，我们需要对索引进行维护，也就是修改，以便于下次查询用户数据的时候可以快速的使用正确的索引。

综上我们可以看出，选择哪种数据结构来存储索引十分重要，这决定了程序的查询效率。而最理想的适合做索引的数据结构，也就是需要具备以下几点：

查询搜索的效率高。O(logn)
数据更新后索引维护的成本低。

2.1 线性结构

如果我们使用线性数据结构来作为索引，比如数组或者链表。那么也就是下面的索引情况：我们需要查询指定的数据时，必须从链表头部开始逐个遍历，查询效率很低。如果使用数组呢？我们直接通过索引下表查询，O(1)!!但是实际上，我们一般查找数据并不知道索引是多少，只是按照一定的条件匹配进行查找，此时并不是按照数值下标直接定位的，所以肯定是不符合大多数业务场景的。另外一点，我们使用线性数据结构来存储索引，每次对索引进行插入的时候，需要重新移动索引的插入位置后续的所有数据的内存位置，这样也是极大的内存开销。即使我们使用二分查找等查询算法，那么也是要求索引数据是有序的，那么在插入的时候维持顺序就是另一个问题了。

2.2 Hash结构

hash结构就是将数据传入hash函数，hash函数会计算出一个和当前值唯一对应的数据结构固定的结果，这个结果作为存储的索引值。但是，无论什么样的hash函数，总是无法避免hash冲突，一旦出现hash冲突，就会导致当前索引处成为线性结构，或者直接将原数据覆盖，因此hash方法也不是理想的索引数据结构。

2.3 二叉搜索树（BST）

二叉搜索树是一种二叉树，其中每个节点的左子树中的值都小于该节点的值，而右子树中的值都大于该节点的值。 BST的中序遍历是有序递增的结果，在平均情况下，二叉搜索树的查找、插入和删除操作的时间复杂度为O(log n)，其中n是树中节点的数量(其实就是类似于二分查找的思想)。

但是，当插入到BST中的数据本身存在一定的有序性，那么就会导致BST变为单向斜树，这个问题我们在介绍AVL的时候也有说过，也就是类似下面的情况：

很明显，这种情况也是变为线性结构了，进而导致索引数据的查询效率降低为变为O(n)。

2.4 AVL树

对于上述BST的问题，根本原因是按照左节点值小于根节点值，右节点值大于根节点值来插入，可能会导致某一侧的书高持续增加，而另一侧基本不变，进而出现一侧线性化，而AVL就是为了解决这个问题的， AVL树是一种自平衡的二叉搜索树，它具有以下特性：

每个节点的左子树和右子树的高度差（平衡因子）不超过1。
每个子树都是AVL树。

AVL树之所以能够自平衡，是因为它在每次插入或删除操作后会通过旋转操作来保持树的平衡性。

关于AVL的详细内容，欢迎参考我之前的笔记

显然，avl可以大大提高查询效率，避免数据线性化，很好的解决了bst的问题。但是，面对插入场景较多的情况，avl树将需要花费大量的时间来进行自动平衡，这样也会降低索引整体的查询和使用效率。

2.5 红黑树

是的，你没有猜错，红黑树就是用来解决avl频繁自动平衡而带来的问题的。红黑树的概念比较复杂，这里我们不详细介绍了，大家可以参考参考文章1 参考文章2 红黑树的规则其实就是使得二叉树不会像AVL那样频繁的进行自动平衡。

下面总结一下红黑树相较于AVL的优化的点：

更少的平衡调整操作：在红黑树中，平衡性的维护相比AVL树更加宽松，这意味着红黑树需要进行的平衡调整操作更少。AVL树在每次插入或删除后都要进行可能的多次旋转操作，以保持树的严格平衡，而红黑树则采用一种更加宽松的平衡条件，因此需要的平衡调整操作较少。
更高的插入和删除性能：由于需要进行的平衡调整操作较少，红黑树的插入和删除操作通常比AVL树更快。这在某些场景下可以带来明显的性能优势，特别是在需要频繁插入和删除操作的情况下。
更低的旋转次数：红黑树的平衡性要求比AVL树更加宽松，因此在旋转操作方面，红黑树通常需要执行的旋转次数较少。这使得红黑树的平衡调整操作更加轻量级，提高了整体性能。
更好的内存利用率：红黑树的平衡性要求相比AVL树更加宽松，这意味着红黑树可能会略微失衡，但是这种失衡是可控的，并且不会严重影响树的性能。由于不需要严格保持平衡，红黑树可能会更好地利用内存空间，减少了节点的旋转和调整次数，提高了内存利用率。

虽然解决了频繁的自动平衡带来的问题，但是当数据量很大的时候，整个红黑树的高度仍然会变得很高，这样会增加查询的次数，数据量很大的时候也会增加io读取的次数。因此红黑树还不是最理想的构建大数据量的索引的数据结构。

2.6 B树/B+树

从上面的BST，AVL或者红黑树，我们都可以看出来，当数据量很大的时候，树高度变得无限高时无法避免的。因为这些都是二叉树，也就是说都是二阶的，每个节点只能有左右两个子节点。那么如果需要保证在大数据量的情况下，树高仍然可控，就需要使用多阶树(多路树)，也就是n叉树。

而B树就是一个有序的多阶树。它可以有效的限制树的高度，使得查找效率增加。下面我们将来详细介绍下B树

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2024/05/03 22:28