红黑树与B+树在存储引擎中的选择
2025/06/29·StepFun can make mistakes, check important info.
linux内核数据结构 红黑树
原文地址： https://www. cnblogs.com/linhaostudy /p/15715244.html
红黑树（Red-Black Tree，RBT）是一种平衡的二叉查找树，前面的红
linux kernel 内核C语言版本红黑树的实现的注释，以及查找、插入的自定义实现
## 背景
经常使用C++语言的程序设计者，可能经常使用虚函数、类模板等来实现自己的设计，但单从性能上来讲，虚函数调用时函数寻址、函数调用等会降低略微的性能，而内核的C语言就是如此的追求极致，得将理论
红黑树
红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J.Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定...
在Linux内核中，红黑树被广泛使用，主要原因在于其高效的平衡性和适用于频繁的插入和删除操作。以下是内核选择红黑树的一些关键原因：
1. 高效的平衡性
红黑树是一种自平衡二叉查找树，通过在每个节点上增加颜色属性（红色或黑色）来确保树的平衡性。红黑树的性质确保了从根到叶子的最长路径不会超过最短路径的两倍，这使得树的高度保持在较低的水平，从而保证了高效的查找、插入和删除操作3。
2. 适用于频繁的插入和删除操作
红黑树在进行插入和删除操作时，通过变色和旋转操作来维持平衡，通常只需要**O(log n)**的时间复杂度。相比之下，AVL树虽然也是平衡二叉树，但在插入和删除操作时需要更多的旋转操作，维护平衡的代价较高。因此，红黑树更适合需要频繁进行插入和删除操作的场景5。
3. 内存管理中的高效应用
在Linux内核的内存管理中，红黑树用于管理虚拟内存区域（VMAs）。由于内存管理需要频繁地进行内存区域的分配和释放，红黑树的高效插入和删除操作使其成为理想的选择\cite{web_5:6}。
4. 进程调度中的使用
Linux内核的**完全公平调度器（CFS）**使用红黑树来管理进程的运行队列。CFS需要频繁地调整进程的优先级和调度顺序，红黑树的高效平衡性和插入删除操作使其非常适合这一场景7。
5. 文件系统中的应用
在EXT3文件系统中，红黑树用于管理目录项。目录项的查找和插入操作非常频繁，红黑树的高效查找和平衡性使其成为合适的选择\cite{web_5:5}。
6. 实现的简洁性和性能优化
Linux内核中的红黑树实现经过了优化，例如通过将颜色信息和父节点指针合并到一个字段中来节省空间\cite{web_10-15}。这种优化使得红黑树在内核中的实现更加简洁和高效。
总结
虽然B+树在大规模数据存储和磁盘访问优化方面有优势，但在Linux内核中，红黑树的高效平衡性、适用于频繁插入删除操作以及在内存管理、进程调度和文件系统中的广泛应用，使其成为内核开发者的首选数据结构。
所以，内存型存储引擎，还是用B+树更好，而不是红黑树？
MySQL为什么使用B+树
## B+树 VS 红黑树
- 红黑树的局限 ：红黑树作为二叉树，树高通常为 O (log₂N)。例如，100 万条数据的红黑树高度约为 20 层，每次查询需要访问 20 次磁盘，效率低下。
-
【数据结构】B树, B+树, B*树, 红黑树, 平衡二叉树
mongo的存储引擎 WiredTiger 实现lazyB树，是一种 B+树变种 （3）区别 mysql 作为关系型数据库，更关注连表查询 mongo 作为文档型数据库，更关注复合字段查询 5、B*树 （1）结构 在B+的非根和非叶子结点，增加指向兄弟的指针 （2）空间利用率 B+树：当一个节点满时，会创建一个新节点，把原节点一半的数据移过去 B*...
红黑树B树B+树区别及其适用场景
## 概述
红黑树B树B+树是我们经常听到的数据结构,在各大组件设计和实现使用的很多,我们只有根本上分析这几种树结构的区别,才能从根本上明白一些组件这样设计的原因.
## 红黑树
1.节点
在内存型存储引擎中，红黑树和跳表是更常见的选择，而不是B+树。以下是详细解释：
1. 高效的平衡性和频繁的插入删除操作
红黑树是一种自平衡二叉查找树，通过在每个节点上增加颜色属性（红色或黑色）来确保树的平衡性。红黑树的性质确保了从根到叶子的最长路径不会超过最短路径的两倍，这使得树的高度保持在较低的水平，从而保证了高效的查找、插入和删除操作。时间复杂度通常为O(log n)4。
内存型存储引擎通常需要频繁地进行插入和删除操作，红黑树在这类操作上的性能优于B+树。例如，Linux内核中的内存管理和进程调度使用红黑树来高效地进行插入、删除和查找操作4。
2. 实现的简洁性和性能优化
红黑树的实现相对简洁，代码量较少，维护和优化更加方便。Linux内核中的红黑树实现经过了优化，例如通过将颜色信息和父节点指针合并到一个字段中来节省空间\cite{web_10-15}。这种优化使得红黑树在内核中的实现更加简洁和高效。
3. 内存友好
红黑树在存储有序数据时，相对于B+树需要更少的额外指针。每个节点除了保存键值对之外，只需要保存指向左右子节点的指针即可。而在B+树中，非叶子节点需要保存更多的子节点指针，这会增加内存占用6。
4. 支持高效的范围查询
虽然B+树在范围查询方面有优势，但红黑树也可以通过中序遍历来支持范围查询操作。在内存型存储引擎中，范围查询的需求可能不如磁盘存储引擎那么强烈，因此红黑树的范围查询能力已经足够满足大多数场景的需求。
5. 适用场景的不同
B+树更适合用于大规模数据存储、磁盘存储系统和需要高效范围查询的场景，如数据库索引1。而红黑树更适合用于内存中的高频增删操作和快速单点查询的场景，如内存型存储引擎3。
6. 为什么Redis选择跳表而不是红黑树？
Redis选择跳表作为有序集合（Sorted Set）的底层实现是基于对性能、内存友好性和简单性的考虑。跳表相对于红黑树具有以下优点：
- 高效的查找和插入性能：跳表通过维护一个多层链表来实现快速跳跃查找，查找和插入操作的时间复杂度为O(log n)7。
- 简单高效的实现：跳表的实现比红黑树更简单，代码量更少，这使得维护和优化变得更加方便7。
- 内存友好：跳表在存储有序数据时，相对于红黑树需要更少的额外指针，内存占用更加节省6。
- 支持高效的范围查询：跳表天然支持范围查询操作，通过多层索引结构可以快速定位到范围内的节点，并进行遍历7。
- 自适应性：跳表的高度是通过随机化的方式进行决策的，这使得它能够根据数据的分布来自适应地调整索引的层数，进一步提高查询效率和内存利用率7。
总结
在内存型存储引擎中，红黑树和跳表是更常见的选择，而不是B+树。红黑树适用于需要频繁进行插入、删除和查找操作的场景，而跳表适用于需要高效范围查询和简单实现的场景。B+树虽然在大规模数据存储和磁盘访问优化方面有优势，但在内存型存储引擎中，其优势并不明显，因此不常用。具体选择取决于应用场景的需求。
