B-树、B+树、Trie树_btrie

July：从B树、B+树、B*树谈到R 树

B-树（B树，B-tree）

产生B树原因：

        大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。

        因为磁盘的操作费时费资源，如果过于频繁的多次查找势必效率低下。那么如何提高效率，即如何避免磁盘过于频繁的多次查找呢？根据磁盘查找存取的次数往往由树的高度所决定，所以，只要我们通过某种较好的树结构减少树的结构尽量减少树的高度，那么是不是便能有效减少磁盘查找存取的次数呢？那这种有效的树结构是一种怎样的树呢？

       这样我们就提出了一个新的查找树结构——多路查找树。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.所有叶子结点位于同一层；

B树的最大高度：

  第一层的根最少有两个孩子，因此第2层至少有两个结点；

  除根和叶子外，其它结点至少有┌m/2┐个孩子；

   因此第3层至少有2 * (┌m/2┐) 个结点；

   因此第4层至少有2 * (┌m/2┐) ^ 2个结点；

   第i层至少有2 * (┌m/2┐)^(i - 2)个结点；

   所以，树中所有的结点个数计算如下图所示：

而除了根结点外，每个结点至少包含┌m/2┐ - 1 个关键字，根结点至少包含一个关键字，当树中关键字总个数是N时，N和树的高度i满足如下的关系：

也就是说含有N个关键字的B树的最大高度i满足 i =  log┌m/2┐((N+1)/2 )+1 （将根结点算作第1层）

搜索：

从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

      1.关键字集合分布在整颗树中；

      2.任何一个关键字出现且只出现在一个结点中；

      3.搜索有可能在非叶子结点结束；

      4.其搜索性能等价于在关键字全集内做一次二分查找；

      5.自动层次控制；

      6.由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为lgN；

      7.B-树的性能总是等价于二分查找（与M值无关），没有B树平衡的问题；

      8.由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的         兄弟结点合并；

B+树

性质：

B+树是B-树的变体，也是一种多路搜索树：

           1.其定义基本与B-树同，除了：

           2.非叶子结点的子树指针与关键字个数相同：含有n个子树的结点中含有n个关键字；而B树中每个结点的指针个数比关键字个数多1个。

           3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；

           4.为所有叶子结点增加一个链指针；增加的顺序访问指针主要是为了加快检索多个相邻叶节点的效率考虑。

           5. 所有关键字都在叶子结点出现；所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)。所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)

B+树上有两个头指针，一个指向根结点，另一个指向关键字最小的结点。因此，B+树可以进行两种查找：一种是从最小关键字开始顺序查找；另一种是从根结点开始，进行随机查找。

搜索：

       B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

        B+的特性：

           1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

           2.不可能在非叶子结点命中；

           3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

           4.更适合文件索引系统；

B*树

   是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；

    定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；

   B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

   B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

        所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

B-树和B+树的应用：数据搜索和数据库索引

参考文章：B-树、B+树、B*树的区别

Trie树

下面是Trie树的简单实现：插入、删除、销毁操作。仅考虑了小写英文字母并且未对输入非法字符进行检测，只是一个测试的小例子：

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <cstring>
#include <iostream>
#define MAXBRANCH 26
using namespace std;
 
struct TrieNode {
	TrieNode * next_branch[MAXBRANCH];
	bool exist;
};
 
TrieNode* CreateTrieNode() {
	TrieNode *node = (TrieNode*)malloc(sizeof(TrieNode));
	node->exist = false;
	memset(node->next_branch, 0, sizeof(node->next_branch));
	return node;
}
 
 
void TrieInsert(TrieNode* root, char* word) {
	TrieNode* node = root;
	int id;
	while (*word) {
		id = *word - 'a';
		if (node->next_branch[id] == NULL)
			node->next_branch[id] = CreateTrieNode();
		node = node->next_branch[id];
		++word;
	}
	node->exist = true; //到达字符串结尾，将其标记为一个串
}
 
//在Trie树中查找word是否存在，存在返回true
//如果查找word是否是某个字符串的前缀，只要将
//返回值值改为return node;即可
bool TrieSearch(TrieNode* root, char *word) {
	TrieNode *node = root;
	int id;
	while (*word && node) {
		id = *word - 'a';
		node = node->next_branch[id];
		++word;
	}
	return (node && node->exist);
}
 
void DestroyTrieTree(TrieNode *root) {
	for (int i = 0; i < MAXBRANCH; i++) {
		if (root->next_branch[i])
			DestroyTrieTree(root->next_branch[i]);
	}
	free(root);
}
 
int main() {
	TrieNode * root = CreateTrieNode();
	char str[100];
	cout << "输入Trie中单词：" << endl;
	while (scanf("%s", str) && strcmp(str, "end") != 0) {
		TrieInsert(root, str);
	}
 
	cout << "输入待匹配的单词：" << endl;
	while (scanf("%s", str) != EOF) {
		if (TrieSearch(root, str))
			cout << "found" << endl;
		else
			cout << "not found" << endl;
	}
}