树结构整体来说分为三层,最上层为根节点,最下层为叶子节点,中间层为非叶子节点
B-树(B-Tree，并不是B“减”树，横杠为连接符，容易被误导)
是一种多路搜索树（并不是二叉的）：
1.定义任意非叶子节点最多只有 M个儿子；且M>2 ；
2.根节点的儿子数为 [2, M](理解为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-树的搜索,从根节点开始,对节点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子节点;重复,直到所有对应的儿子指针为空,或已经是叶子节点
B-树的特性：
1,关键字集合分布在整棵树中;
2,任何关键字出现且只出现在一个节点中;
3,搜索有可能在非叶子节点结束;
4,其搜索性能等价于在关键字内做一次二分查找;
5,自动层次控制;
由于限制了除根节点以外的非叶子节点,至少含有M/2个儿子,确保了节点的至少利用率,其最底搜索性能为:
B+树
B+树是 B-树的变体，也是一种多路搜索树：
其定义基本与B- 树同，除了：
1.非叶子节点的子树指针与关键字个数相同；
2,非叶子节点的子树指针P[i],指向的关键字值属于[K[i],K[i+1])的子树;
3,为所有叶子节点增加一个链指针
4,所有关键字都在叶子节点出现
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+树要低,空间使用率要高
红黑树
R-B Tree，全称是Red-Black Tree ，又称为“红黑树” ，它是一种特殊的二叉查找树.红黑树的每个节点上都有存储位表示节点的颜色;
红黑树的特性:
1,每个节点都是黑色或者是红色.
2,根节点是黑色.
3,每个叶子节点(NIL)是黑色.(这里的叶子节点,是指为空(NIL或NULL)的叶子节点)
4,如果一个节点为红色的,则它的子节点必须是黑色的.
5,从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点(没有一条路径会比其他路径长出2倍,因而,红黑树是相对接近平衡的二叉树)
节点属性:key,3个指针:parent,lchild,rchild,color
红黑树是二叉搜索树的改进.我们知道二叉搜索树在最坏的情况下可能会变成一个链表(当所有节点从小到大依次插入后).而红黑树每一次插入和删除节点之后都会花O(logN)的时间来对树的结构进行修改,以保持树的平衡.也就是说,红黑树的查找方法与二叉搜索树完全一样;
二叉树
二叉树是每个节点是最多有两个子树的树结构,它有五种基本形态:二叉树可以是空集;根可以有空的左子树和右子树;或者左右子树皆为空;
特点:
1,二叉树第i层上的节点数目最多为2{i-1} (i≥1)
2,深度为k的二叉树至多有2{k}-1个结点(k≥1)。
3,包含n个结点的二叉树的高度至少为log2 (n+1)。
4,在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为 n2，则n0=n2+1。
二叉树又分为:满二叉树,完全二叉树和二叉查找树,这里就不一一列举了
小结
B树：二叉树，每个节点只存储一个关键字，等于则命中，小于走左节点，大于
走右节点；
B-树：多路搜索树，每个节点存储 M/2到M 个关键字，非叶子节点存储指向关键
字范围的子节点；
所有关键字在整颗树中出现，且只出现一次，非叶子节点可以命中；
B+树：在 B-树基础上，为叶子节点增加链表指针，所有关键字都在叶子节点
中出现，非叶子节点作为叶子节点的索引；B+ 树总是到叶子节点才命中；
B*树：在 B+树基础上，为非叶子节点也增加链表指针，将节点的最低利用率
从1/2提高到 2/3；
更多学习笔记请关注公众号
