(3)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.更适合文件索引系统;

　　(4)B*树

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

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

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

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

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

　　(5)红黑树

　　红黑树(Red-Black Tree)是二叉搜索树(BinarySearch Tree)的一种改进。我们知道二叉搜索树在最坏的情况下可能会变成一个链表(当所有节点按从小到大的顺序依次插入后)。而红黑树在每一次插入或删除节点之后都会花O(log N)的时间来对树的结构作修改，以保持树的平衡。也就是说，红黑树的查找方法与二叉搜索树完全一样;插入和删除节点的的方法前半部分节与二叉搜索树完全一样，而后半部分添加了一些修改树的结构的操作。

　　map就是采用红黑树存储的，红黑树(RB Tree)是平衡二叉树，其优点就是树到叶子节点深度一致，查找的效率也就一样，为logN。在实行查找，插入，删除的效率都一致，而当是全部静态数据时，没有太多优势，可能采用hash表各合适。

　　相对来说，hash_map是一个hashtable占用内存更多，查找效率高一些，但是hash的时间比较费时。总体而言，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小无关，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小， hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且 hash_map的构造速度较慢。

　　现在知道如何选择了吗?权衡三个因素: 查找速度, 数据量, 内存使用。

　　红黑树的每个节点上的属性除了有一个key、3个指针：parent、lchild、rchild以外，还多了一个属性：color。它只能是两种颜色：红或黑。而红黑树除了具有二叉搜索树的所有性质之外，还具有以下4点性质：

　　1. 根节点是黑色的。

　　2. 空节点是黑色的(红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL，而是指向一个定义好的空节点)。

　　3. 红色节点的父、左子、右子节点都是黑色。

　　4. 在任何一棵子树中，每一条从根节点向下走到空节点的路径上包含的黑色节点数量都相同。