红黑树与B+树在存储引擎中的选择
2025/06/29·StepFun can make mistakes, check important info.
红黑树
红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J.Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定...
Linux内核红黑树算法的实现详解（含实例源码）
Linux内核红黑树的算法都定义在./include/linux/rbtree.h和./lib/rbtree.c两个文件中。1、结构体 struct rb_node { unsigned long rb_parent_color;define RB_RED 0 define RB_BLACK 1 struct rb_node*rb_right;struct rb_node*rb_left;}_attribute_((aligned(sizeof(long))));这里的巧...
linux内核数据结构之红黑树
红黑树的统计性能好于平衡二叉树（AVL树），因此在内核中也有很多应用。在linux非实时调度中的应用 在linux虚拟内存中的应用 AVL树和红黑树都是基于BST树(二叉搜索树)，对于只读操作均和BST树相同，但BST树连续插入顺序递增或递减会导致BST树退化成链表，性能大幅度降低。因此，AVL树 和 红...
在Linux内核中，红黑树被广泛使用，主要原因在于其高效的平衡性和适用于频繁的插入和删除操作。以下是内核选择红黑树的一些关键原因：
1. 高效的平衡性
红黑树是一种自平衡二叉查找树，通过在每个节点上增加颜色属性（红色或黑色）来确保树的平衡性。红黑树的性质确保了从根到叶子的最长路径不会超过最短路径的两倍，这使得树的高度保持在较低的水平，从而保证了高效的查找、插入和删除操作1。
2. 适用于频繁的插入和删除操作
红黑树在进行插入和删除操作时，通过变色和旋转操作来维持平衡，通常只需要**O(log n)**的时间复杂度。相比之下，AVL树虽然也是平衡二叉树，但在插入和删除操作时需要更多的旋转操作，维护平衡的代价较高。因此，红黑树更适合需要频繁进行插入和删除操作的场景3。
3. 内存管理中的高效应用
在Linux内核的内存管理中，红黑树用于管理虚拟内存区域（VMAs）。由于内存管理需要频繁地进行内存区域的分配和释放，红黑树的高效插入和删除操作使其成为理想的选择\cite{web_5:6}。
4. 进程调度中的使用
Linux内核的**完全公平调度器（CFS）**使用红黑树来管理进程的运行队列。CFS需要频繁地调整进程的优先级和调度顺序，红黑树的高效平衡性和插入删除操作使其非常适合这一场景5。
5. 文件系统中的应用
在EXT3文件系统中，红黑树用于管理目录项。目录项的查找和插入操作非常频繁，红黑树的高效查找和平衡性使其成为合适的选择\cite{web_5:5}。
6. 实现的简洁性和性能优化
Linux内核中的红黑树实现经过了优化，例如通过将颜色信息和父节点指针合并到一个字段中来节省空间\cite{web_10-15}。这种优化使得红黑树在内核中的实现更加简洁和高效。
总结
虽然B+树在大规模数据存储和磁盘访问优化方面有优势，但在Linux内核中，红黑树的高效平衡性、适用于频繁插入删除操作以及在内存管理、进程调度和文件系统中的广泛应用，使其成为内核开发者的首选数据结构。
所以，内存型存储引擎，还是用B+树更好，而不是红黑树？
【数据结构】B树, B+树, B*树, 红黑树, 平衡二叉树
mongo的存储引擎 WiredTiger 实现lazyB树，是一种 B+树变种 （3）区别 mysql 作为关系型数据库，更关注连表查询 mongo 作为文档型数据库，更关注复合字段查询 5、B*树 （1）结构 在B+的非根和非叶子结点，增加指向兄弟的指针 （2）空间利用率 B+树：当一个节点满时，会创建一个新节点，把原节点一半的数据移过去 B*...
红黑树
红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J.Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。红黑树是一种特化的AV...
磁盘存储下红黑树、B 树与 B + 树的原理、操作及对比
提升数据访问速度：相比硬盘等外部存储设备，内存访问速度极快。CPU 能直接快速读取和写入内存中的数据，无需像访问硬盘那样经过复杂机械操作，从而加快程序运行速度。支持多任务处理：计算机同时运行多个程序时，内存为每个程序分配空间，操作系统负责管理，确保程序间互不冲突。特性 易失性：断电后内存中数据会立即丢失，所以仅用于临时存储。随机访问：CPU 可随机快速访问内存中任一位置的数据。数据读...
在内存型存储引擎中，红黑树和跳表是更常见的选择，而不是B+树。以下是详细解释：
1. 高效的平衡性和频繁的插入删除操作
红黑树是一种自平衡二叉查找树，通过在每个节点上增加颜色属性（红色或黑色）来确保树的平衡性。红黑树的性质确保了从根到叶子的最长路径不会超过最短路径的两倍，这使得树的高度保持在较低的水平，从而保证了高效的查找、插入和删除操作。时间复杂度通常为O(log n)2。
内存型存储引擎通常需要频繁地进行插入和删除操作，红黑树在这类操作上的性能优于B+树。例如，Linux内核中的内存管理和进程调度使用红黑树来高效地进行插入、删除和查找操作2。
2. 实现的简洁性和性能优化
红黑树的实现相对简洁，代码量较少，维护和优化更加方便。Linux内核中的红黑树实现经过了优化，例如通过将颜色信息和父节点指针合并到一个字段中来节省空间\cite{web_10-15}。这种优化使得红黑树在内核中的实现更加简洁和高效。
3. 内存友好
红黑树在存储有序数据时，相对于B+树需要更少的额外指针。每个节点除了保存键值对之外，只需要保存指向左右子节点的指针即可。而在B+树中，非叶子节点需要保存更多的子节点指针，这会增加内存占用4。
4. 支持高效的范围查询
虽然B+树在范围查询方面有优势，但红黑树也可以通过中序遍历来支持范围查询操作。在内存型存储引擎中，范围查询的需求可能不如磁盘存储引擎那么强烈，因此红黑树的范围查询能力已经足够满足大多数场景的需求。
5. 适用场景的不同
B+树更适合用于大规模数据存储、磁盘存储系统和需要高效范围查询的场景，如数据库索引。而红黑树更适合用于内存中的高频增删操作和快速单点查询的场景，如内存型存储引擎。
6. 为什么Redis选择跳表而不是红黑树？
Redis选择跳表作为有序集合（Sorted Set）的底层实现是基于对性能、内存友好性和简单性的考虑。跳表相对于红黑树具有以下优点：
- 高效的查找和插入性能：跳表通过维护一个多层链表来实现快速跳跃查找，查找和插入操作的时间复杂度为O(log n)5。
- 简单高效的实现：跳表的实现比红黑树更简单，代码量更少，这使得维护和优化变得更加方便5。
- 内存友好：跳表在存储有序数据时，相对于红黑树需要更少的额外指针，内存占用更加节省4。
- 支持高效的范围查询：跳表天然支持范围查询操作，通过多层索引结构可以快速定位到范围内的节点，并进行遍历5。
- 自适应性：跳表的高度是通过随机化的方式进行决策的，这使得它能够根据数据的分布来自适应地调整索引的层数，进一步提高查询效率和内存利用率5。
总结
在内存型存储引擎中，红黑树和跳表是更常见的选择，而不是B+树。红黑树适用于需要频繁进行插入、删除和查找操作的场景，而跳表适用于需要高效范围查询和简单实现的场景。B+树虽然在大规模数据存储和磁盘访问优化方面有优势，但在内存型存储引擎中，其优势并不明显，因此不常用。具体选择取决于应用场景的需求。
