红黑树和B树应用场景
红黑树和B树应用场景有何不同？
2者都是有序数据结构，可用作数据容器。
红黑树多用在内部排序，即全放在内存中的，微软STL的map和set的内部实现就是红黑树。
B树多用在内存里放不下，大部分数据存储在外存上时。因为B树层数少，因此可以确保每次操作，读取磁盘的次数尽可能的少。
在数据较小，可以完全放到内存中时，红黑树的时间复杂度比B树低。
反之，数据量较大，外存中占主要部分时，B树因其读磁盘次数少，而具有更快的速度。
红黑树，B树，B+树，B-树 理解
红黑树rbtree 二叉排序树
map 就是采用红黑树存储的，红黑树(RB Tree)是平衡二叉树，其优点就是树到叶子节点深度一致，查找的效率也就一样，为logN.在实行查找，插入，删除的效率都一致，而当是全部静态数据时，没有太多优势，可能采用hash表各合适。
hash_map是一个hash table占用内存更多，查找效率高一些，但是hash的时间比较费时。
总 体来说，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小， hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且 hash_map的构造速度较慢。
现在知道如何选择了吗？权衡三个因素: 查找速度, 数据量, 内存使用。
trie树Double Array 字典查找树
Trie树既可用于一般的字典搜索，也可用于索引查找。
每个节点相当于DFA的一个状态，终止状态为查找结束。有序查找的过程相当于状态的不断转换
对于给定的一个字符串a1,a2,a3,...,an.则
采用TRIE树搜索经过n次搜索即可完成一次查找。不过好像还是没有B树的搜索效率高，B树搜索算法复杂度为logt(n+1/2).当t趋向大，搜索效率变得高效。怪不得DB2的访问内存设置为虚拟内存的一个PAGE大小，而且帧切换频率降低，无需经常的PAGE切换。
B树
即二叉搜索树：
1.所有非叶子结点至多拥有两个儿子（Left和Right）；
2.所有结点存储一个关键字；
3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；
如：
B树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；
如果B树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变B树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；
如：
但B树在经过多次插入与删除后，有可能导致不同的结构：
右边也是一个B树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的树结构索引；所以，使用B树还要考虑尽可能让B树保持左图的结构，和避免右图的结构，也就是所谓的“平衡”问题；
实际使用的B树都是在原B树的基础上加上平衡算法，即“平衡二叉树”；如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键；平衡算法是一种在B树中插入和删除结点的策略；
B-树
是一种多路搜索树（并不是二叉的）：
1.定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8.所有叶子结点位于同一层；
如：（M=3）
B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；
B-树的特性：
1.关键字集合分布在整颗树中；
2.任何一个关键字出现且只出现在一个结点中；
3.搜索有可能在非叶子结点结束；
4.其搜索性能等价于在关键字全集内做一次二分查找；
5.自动层次控制；
由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为：
其中，M为设定的非叶子结点最多子树个数，N为关键字总数；
所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；
由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并；
B+树
B+树是B-树的变体，也是一种多路搜索树：
1.其定义基本与B-树同，除了：
2.非叶子结点的子树指针与关键字个数相同；
3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
5.为所有叶子结点增加一个链指针；
6.所有关键字都在叶子结点出现；
如：（M=3）
B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；
B+的特性：
1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2.不可能在非叶子结点命中；
3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
4.更适合文件索引系统；
B*树
是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；
B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；
所以，B*树分配新结点的概率比B+树要低，空间使用率更高；
小结
B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；
所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；
B树是为了提高磁盘或外部存储设备查找效率而产生的一种多路平衡查找树。
B+树为B树的变形结构，用于大多数数据库或文件系统的存储而设计。
B树相对于红黑树的区别
在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下的情况。为什么会出现这样的情况，我们知道要获取磁盘上数据，必须先通过磁盘移动臂移动到数据所在的柱面，然后找到指定盘面，接着旋转盘面找到数据所在的磁道，最后对数据进行读写。磁盘IO代价主要花费在查找所需的柱面上，树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定，所以，只要我们通过某种较好的树结构减少树的结构尽量减少树的高度，B树可以有多个子女，从几十到上千，可以降低树的高度。
B树和B+树的区别
B树所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息。
B+树所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接，所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)
为什么说B+比B树更适合实际应用中操作系统的文件索引和数据库索引？
1) B+的磁盘读写代价更低
B+的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
2) B+-tree的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
数据库索引采用B+树的主要原因是 B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）
作者：benpaobagzb
来源：CSDN
原文：https://blog.csdn.net/benpaobagzb/article/details/50805711
版权声明：本文为博主原创文章，转载请附上博文链接！
Linux kernel rbtree
因编写内核模块时需要用到rbtree来记录异步request，研究分析了一下kernel rbtree的使用方法，记录于此。本文主要参考了内核文档rbtree.txt
rbtree简介
Red-black trees（rbtree）是一种自平衡的二叉搜索树，用于存储可分类的key/value数据对。它不同于radix trees或者hash tables。
radix trees用于有效存储稀疏数组（使用长整型索引进行节点的插入、查询和删除），其索引值太大无法用数组直接存储。
hash tables用于散列索引缩小查询的范围，但它没有做排序，因此不能快速的定位。
Red-black trees和AVL trees很相似，但是提供了最坏情况下更快的实时插入和删除性能。插入最多2次rotations、删除最多3次rotations即可完成tree的重平衡。不过相比AVL trees，其查询时间稍慢（O(log n)）。
Linux内核大量使用rbtree，如：I/O调度算法deadline和CFQ使用rbtree来跟踪request；高精度定时器代码使用rbtree来组织定时任务；ext3文件系统使用rbtree来跟踪目录entry；等等。
rbtree使用方法
内核rbtree的实现在文件"lib/rbtree.c"，使用rbtree需要包含头文件：
#include <linux/rbtree.h>
为了提高性能，linux rbtree比传统的tree实现了更少的中间层。rbtree的节点结构体struct rb_node直接嵌入到使用者的data structure（传统的方法是通过指针指向了data structure）。rbtree的插入和查询函数由使用者通过调用linux rbtree提供的基础函数自己实现（传统的方法是提供回调函数指针）。并且btree的锁也由使用者自己管理。
创建rbtree
在data数据结构里定义struct rb_node：
struct mytype {
struct rb_node node;
char *keystring;
};
当处理rbtree的节点时，通过container_of()宏定义找到data数据结构指针。keystring为rbtree的key，可以定义为字符串或者整型，它将用于用户自定义的排序和查找。
然后定义rbtree的root节点：
struct rb_root mytree = RB_ROOT;
查找rbtree
使用者自己实现rbtree的查找函数，通过如下方法：从root开始，比较key的值，然后根据需要查找left节点或者right节点。
struct mytype *my_search(struct rb_root *root, char *string)
{
struct rb_node *node = root->rb_node;
while (node) {
struct mytype *data = container_of(node, struct mytype, node);
int result;
result = strcmp(string, data->keystring);
if (result < 0)
node = node->rb_left;
else if (result > 0)
node = node->rb_right;
else
return data;
}
return NULL;
}
插入新节点
使用者自己实现rbtree的插入函数，先找到插入的位置（该位置为NULL），然后插入新的节点并执行rbtree的重平衡。在查找到插入位置时，需要其parent节点的link用于rbtree的重平衡。
int my_insert(struct rb_root *root, struct mytype *data)
{
struct rb_node **new = &(root->rb_node), *parent = NULL;
/* Figure out where to put new node */
while (*new) {
struct mytype *this = container_of(*new, struct mytype, node);
int result = strcmp(data->keystring, this->keystring);
parent = *new;
if (result < 0)
new = &((*new)->rb_left);
else if (result > 0)
new = &((*new)->rb_right);
else
return FALSE;
}
/* Add new node and rebalance tree. */
rb_link_node(&data->node, parent, new);
rb_insert_color(&data->node, root);
return TRUE;
}
删除/覆盖节点
通过如下函数删除和覆盖一个节点：
void rb_erase(struct rb_node *victim, struct rb_root *tree);
void rb_replace_node(struct rb_node *old, struct rb_node *new, struct rb_root *tree);
覆盖一个节点并不会重平衡rbtree，因此必须保证new和old的key是一样的，否者会导致异常。
删除一个节点代码示例：
struct mytype *data = mysearch(&mytree, "walrus");
if (data) {
rb_erase(&data->node, &mytree);
myfree(data);
}
按顺序遍历rbtree
如下4个函数用于顺序遍历rbtree：
struct rb_node *rb_first(struct rb_root *tree);
struct rb_node *rb_last(struct rb_root *tree);
struct rb_node *rb_next(struct rb_node *node);
struct rb_node *rb_prev(struct rb_node *node);
代码示例：
struct rb_node *node;
for (node = rb_first(&mytree); node; node = rb_next(node))
printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);
rbtree.h中删除#include 和#include 两行，添加#include
对于rb_node的声明删除掉最后的__attribute__((aligned(sizeof(long))))
最后在rbtree.h中添加如下一些宏定义：
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif
#define container_of(ptr, type, member) ({ /
const typeof( ((type *)0)->member ) *__mptr = (ptr); /
(type *)( (char *)__mptr - offsetof(type,member) );})
在使用rbtree的时候，每个rbtree的元素都由使用者自己定义如：
struct my_item
{
struct rb_node node;
struct my_data_struct data;
};
其中的struct my_data_struct是自己的数据区域
struct my_data_struct
{
long key;
long value;
};
下面需要实现两个函数，第一个是一个search函数，形式如下：
struct my_item* _my_rbtree_search (struct rb_root* root, long key);
其中的root参数是根节点指针；key是关键字，rbtree根据它来排序以及查找。
该函数的实现如下：
struct my_item* _my_rbtree_search (struct rb_root* root, long key)
{
struct rb_node *node;
struct my_item* item;
node = root->rb_node;
while (node)
{
item = rb_entry (node, struct my_item, node);
if (item->data.key > key)
node = node->rb_left;
else if (item->data.key < key)
node = node->rb_right;
else
{
return item; /* found it */
}
}
return NULL;
}
下面还需要实现一个插入的函数：
void _my_rbtree_insert (struct rb_root* root, struct my_item* item)
{
struct rb_node **link, *parent;
long value;
struct my_item* p_item;
link = &(root->rb_node);
value = item->data.key;
/* Go to the bottom of the tree */
while (*link)
{
parent = *link;
p_item = rb_entry(parent, struct my_item, node);
if (p_item->data.key > value)
link = &((*link)->rb_left);
else if (p_item->data.key < value)
link = &((*link)->rb_right);
else
return;
}
/* Put the new node there */
rb_link_node(&(item->node), parent, link);
rb_insert_color(&(item->node), root);
}
拥有了以上两个函数我们就可以实现search、insert、remove、modify、traverse等操作，下面给出大概的伪代码吧
struct my_data_struct search (struct rb_root* root, long key)
{
struct my_data_struct data;
struct my_item *item;
memset (&data, 0, sizeof(struct my_data));
item = _my_rbtree_search (root, key);
if (NULL != item)
{
memcpy (&data, item->data, sizeof(struct my_data_struct));
}
return data;
}
int insert (struct rb_root* root, long key, long value)
{
struct my_item *item = (struct my_item*) malloc (sizeof(struct my_item));
if (NULL == item)
{
return -1;
}
item->data.key = key;
item->data.value = value;
_my_rbtree_insert (root, item);
return 0;
}
int remove (struct rb_root* root, long key)
{
struct my_item* item;
item = _my_rbtree_search (root, key);
if (NULL != item)
{
rb_erase (&(item->node), root);
}
return 0;
}
int modify (struct rb_root* root, long key, long new_value)
{
struct my_item* item;
item = _my_rbtree_search (root, key);
if (NULL != item)
{
item->data.value = new_value;
}
return 0;
}
int traverse (struct rb_root* root)
{
struct rb_node* node;
struct my_item* item;
for (node = rb_first (root); node; node = rb_next (node))
{
item = rb_entry (node, struct my_item, node);
printf ("key:%d/tvalue:%d/n", item->data.key, item->data.value);
}
return 0;
}