我们知道的数据结构中树有什么样子的,但是具体是有什么东西你们了解吗?
下面我们就来仔细的梳理一下什么是树
树
树（tree）是包含n（n>=0）个结点的有穷集，其中：
（1）每个元素称为结点（node）；
（2）有一个特定的结点被称为根结点或树根（root）。
（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。
这就是一个树,(我从百度上直接挡的)
然后就是一些基本的概念
树状图是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
有且只有一个结点没有前驱,该结点被称为树的根
除了根结点以外,其余各个结点有且只有一个前驱
包括根结点以内的每一个结点,可以由任意多个后继(含0个)
树的度
度是什么意思呢?分为节点的度和树的度
节点的度是指每个结点拥有的子树数或者是后继结点数定义为该结点的度,树中所有结点的度的最大值被定义为树的度,
比如说在上图中,结点C的度是3,结点B的度是2,整棵树的度也是为3.
分支节点和叶子结点
在一棵树中，度等于0的结点称之为叶子结点或者终端结点，度大于0的结点称作分支节点或者非终端结点
孩子节点，双亲结点，兄弟结点
在一棵树中，每个结点的子树的根，或者每个结点的后继，被习惯的称为该结点的孩子、儿子、子女，相应的该结点被称作孩子结点的双亲、父亲或者母亲。具有同一双亲的孩子互称兄弟。一个结点的所有子树的。
结点的层数和树的深度
树是一种递归结构，也是一种层次结构，结点的层数是从树根开始定义的，根节点为第一层，他的孩子是第二层，树中所有结点最大层数称为树的深度或者高度。
有序树和无序树
若树中各结点的子树是按照一定的次序从有左向右排列，则成为有序树，反之称为无序树。在上图中，如果看成是有序树则这两棵树不相同，如果看成是无序树，则两棵树是相同的。
二叉树
二叉树是树的一种，也是树的主要应用，二叉树是n(n>0)个结点的有限的集合，该集合或者为空集或者由一个根节点和两棵互不相交分别为根节点的左子树和右子树的二叉树构成。
二叉树的特点
每个结点最多两个子树
二叉树是有序的
二叉树的种类
满二叉树，完全二叉树，平衡二叉树，二叉搜索树，红黑树
满二叉树（Full Binary Tree）
所有结点都存在左子树和右子树，且所有叶子结点都在同一层
如图，左边的就是满二叉树，右边的不是，因为他们的叶子结点不在同一层
完全二叉树（Complete Binary Tree）
对一棵具有n个结点的二叉树按层序进行编号，如果编号为i(1<=i<=n)的结点与相同深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则称这棵二叉树称为完全二叉树，显然一颗满二叉树一定是一课完全二叉树
左边是一个完全二叉树，右边不是完全二叉树。
二叉搜索树（Binary Search Tree）
又称二叉查找树、二叉排序树（Binary Sort Tree）。
特点
若其左子树存在，则其左子树中每个节点的值都不大于该节点值；
若其右子树存在，则其右子树中每个节点的值都不小于该节点值。
左右子树分别为二叉搜索树
二叉搜索时的时间复杂度是 O(log2(n))这就是一个二叉搜索树
平衡二叉树（Balanced Binary Tree）
平衡二叉查找树：简称平衡二叉树。由前苏联的数学家Adelse-Velskil和Landis在1962年提出的高度平衡的二叉树，根据科学家的英文名也称为AVL树。它具有如下几个性质：
可以是空树。
假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过1
平衡之意，如天平，即两边的分量大约相同。如定义，假如一棵树的左右子树的高度之差超过1，如左子树的树高为2，右子树的树高为0，子树树高差的绝对值为2就打破了这个平衡。
也是为了解决二叉搜索树的问题，我们之所以使用二叉搜索树是因为二叉搜索树可以节省我们的运算次数，二叉搜索时的时间复杂度是 O(log2(n))，但是二叉搜索树容易遇到问题，例如说下图
因为他是每一层只有一个所以还是很耗费系统资源，而且使用了没有意义的一个结构我们要使用方法去避免这种情况，我们使用左旋和右旋技术解决
具体的方法我们通过一个动图来解决
图的来源
在这里也是描述了AVL树和红黑树接一下动图
在这里我们来处理一下我们之前的问题
先进行一步转化，变成这个样子然后
这就是最后的变成的样子，这样就完成一个平衡二叉树
红黑树（Red Black Tree）
是每个节点都带有颜色属性（颜色为红色或黑色）的自平衡二叉查找树，满足下列性质：
1）节点是红色或黑色；
2）根节点是黑色；
3）所有叶子节点都是黑色；
4）每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
5）从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
如图
红黑树其实是AVL树的一种，也是会有旋转平衡，但是要根据从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
为什么要使用红黑树呢？或者说红黑树能够解决什么样子的问题呢？
它可以在O（lgn）时间内做查找，插入和删除，也是在最坏的情况的下进行的这些操作，这也是保证了红黑树的最长路径不会超过最短路径的两倍.
红黑树牺牲了严格的高度平衡为条件，要求部分达标即可，由于它的设计，红黑树在很短的时间内就会变得平衡，而且相对于二叉查找树（BST）书的最长路径不会大于最短路径两倍，保证了最低的查找效果，最坏的情况是O（lgn），比二叉搜索树可以多得是效率，红黑树只是需要进行局部的转换，而并不是像二叉平衡树一样，红黑树的算法时间复杂度和AVL几乎相同，但是统计性能更加的高，红黑树的维护（增删改差）要AVL要耗时少，查找效率相同。
B树
在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。-----------维基百科
2-3树，2-3-4数
这些分别是是B树的一种，2-3树，2-3-4树中2，3，4指的是结点数，分别指的是2结点，3结点，4结点。
在2结点中包含一个元素和两个孩子（或者没有孩子）。左子树包含的结点的元素小于该结点的元素值，右子树包含的结点的元素大于该结点的元素值。2结点要不就有两个孩子要不没有孩子，不允许有一个孩子。
在3结点中包含一个大一个小两个元素和三个孩子（或者没有孩子）。左子树包含的结点的元素小于该结点较小的元素值，右子树包含的结点的元素大于该结点较大的元素值，中间子树包含的结点的元素值介于两个元素之间的值。3结点要不就有三个孩子要不没有孩子，不允许有一个孩子或者两个孩子。
在4结点中包含小中大元素和四个孩子（或者没有孩子）。最左子树包含的结点的元素小于该结点最小的元素值，第二个子树包含的结点的元素值介于大于最小小于中间，第三个子树子树包含的结点的元素大于该结点的中间元素值，小于最大的元素值，最右子树包含的结点的值包含的大于该结点的最大的元素值。4结点要不就有四个孩子要不没有孩子，不允许有一个孩子或者两个孩子或者三个孩子。
这两种的所有的树的叶子结点都在同一层次。
B树详解
B树是一种多路查找树， B树也称B-树,它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数，我们把树中结点最大的孩子数目称为B树的阶，通常记作m。
一棵m阶树要么为空树，要么有以下的性质
【1】树中的每个结点至多有m棵子树（每个结点最多有m-1个关键字。（两个子树指针夹着一个关键字））
【2】若根结点不是终端结点，则至少有两棵子树（根结点最少可以只有1个关键字。）
【3】除根结点以外的所有非叶节点至少有【m/2】（向上取整，我没有办法打了）棵子树（非根结点至少有Math.ceil(m/2)-1个关键字。）
【4】所有分业结点的结构如下
其中ki【i=1,2,3,4,5】为结点的关键字，且满足k1<k2<…<kn
其中Pi【i=1,2,3,4,5】为指向子树根结点的指针，且满足Pi-1所指向的子树的所有结点的关键字都小于ki
Pi所指向的子树的所有结点的关键字都小于ki+1
n为结点中关键字的个数
（每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。）
【5】所有的叶子结点出现在同一层次上，就像是null（就像是折半查找失败的结点）（所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。）
为什么要使用过B树（和红黑树的区别）
（1）计算机有一个局部性原理，就是说，当一个数据被用到时，其附近的数据也通常会马上被使用。
（2）所以当你用红黑树的时候，你一次只能得到一个键值的信息，而用B树，可以得到最多M-1个键值的信息。这样来说B树当然更好了。
（3）另外一方面，同样的数据，红黑树的阶数更大，B树更短，这样查找的时候当然B树更具有优势了，效率也就越高。对于B树，我们首先要知道它的应用，B树大量应用在数据库和文件系统当中。
B树是对二叉查找树的改进。它的设计思想是，将相关数据尽量集中在一起，以便一次读取多个数据，减少硬盘操作次数。B树为系统最优化大块数据的读和写操作。B树算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。
假定一个节点可以容纳100个值，那么3层的B树可以容纳100万个数据，如果换成二叉查找树，则需要20层！假定操作系统一次读取一个节点，并且根节点保留在内存中，那么B树在100万个数据中查找目标值，只需要读取两次硬盘。B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。
B树特性
B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。
关键字集合分布在整颗树中；
任何一个关键字出现且只出现在一个结点中；
搜索有可能在非叶子结点结束；
其搜索性能等价于在关键字全集内做一次二分查找；
B树问答题
什么是B树？B树有什么特征？
答：一棵度为m（也称为m阶，m为给定数）的B-树，它满足：
（1）每个结点的子结点个数≤m；
（2）根结点若不是叶子结点，它至少有两个子结点；
（3）除根和叶子结点外，每个结点的子结点个数≥ ceil(m/2)；(注：ceil为向上取整函数）
（4）所有的叶子结点都出现在同一层，而且不带有信息；
（5）非叶子结点若具有j+1个子结点，那么它包含j个关键字。其中，j≤m-1。B-树的非叶子结点的结构形式如下：
BTree结点内容结构
ki (1≤i≤j)是关键字，所有关键字的值是唯一的；
pi (0≤i≤j)是指向该结点的子结点的指针。
结点中的关键字是按一定规则排好序的。假若按升序排列，有k1 < k2 < … < kj，那么，p0指向一棵关键字均小于k1的子树的根结点； pi（0
一个完整的B树结构
B树的查找是如何实现的？
答：在给定的m阶B树中查找一个给定值v相等的关键字，必须从根结点开始进行查找。
B树应用于文件系统的动态索引结构，这些结点存储于外部存储设备上。当一个结点从外存调入内存后，我们可就这个结点的关键字序列，使用顺序查找（m较小时），或使用二分查找（ m较大时）。
假若当前被查找的结点中有j个关键字，那么，在查找等于给定值v的关键字时，会有如下可能：
（1）若v==ki (1≤i≤j)，则查找成功。
（2）若v < k1 ,则
① 如果p0为空，那么查找失败；
② 如果p0非空，那么从外存取得p0所指的结点，再继续进行查找。
（3）若ki
① 如果pi为空，那么查找失败；
② 如果pi非空，那么从外存取得pi所指的结点，再继续进行查找。
（4）若kj
① 如果pj为空，那么查找失败；
② 如果pj非空，那么从外存取得pj所指的结点，再继续进行查找。
既然查找效率与树的高度紧密相关，那么B树的高度由什么决定？
答：若n≥1，m≥3，则对任意一棵具有n个关键字的m阶B树，其树高h至多为：
logt((n+1)/2)+1。
这里t是每个(除根外)内部结点的最小度数，即
t是每个(除根外)内部结点的最小度数，
B-树的高度为O(logtn)。
给个B树性能分析具体例子呗？
答：首先须知：n个结点的二叉平衡的高度H（即lgn）比B树的高度h约大lgt倍，t为B树内部结点的最小度数ceil(m/2)。
【例】若阶m=1024，则lgt=lg512=9。此时若B树高度为4，则平衡的二叉排序树的高度约为36。显然，若m越大，则B树高度越小。
若要作为内存中的查找表，B树的表现还要比二叉平衡树好吗？
答：非也。若要作为内存中的查找表，B树却不一定比平衡的二叉排序树好，尤其当m较大时更是如此。
因为查找等操作的CPU计算时间在B树上是
O(mlogtn)=O(lgn·(m/lgt))
而m/lgt>1，所以m较大时O(mlogtn)比平衡的二叉排序树上相应操作的时间O(lgn)大得多。因此，仅在内存中使用的B树必须取较小的m。（通常取最小值m=3，此时B树中每个内部结点可以有2或3个孩子，这种3阶的B树称为2-3树）。
B+树特征
b+树，是b树的一种变体，查询性能更好。m阶的b+树的特征：
有n棵子树的非叶子结点中含有n个关键字（b树是n-1个），这些关键字不保存数据，只用来索引，所有数据都保存在叶子节点（b树是每个关键字都保存数据）。
所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
所有的非叶子结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字。
通常在b+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。
同一个数字会在不同节点中重复出现，根节点的最大元素就是b+树的最大元素。
b+树相比于b树的查询优势：
B+树的优势在于查找效率上，具体说明：
首先，Ｂ＋树的查找和Ｂ树一样，类似于二叉查找树。起始于根节点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。在节点内部典型的使用是二分查找来确定这个位置。
（1）不同的是，Ｂ＋树中间节点没有卫星数据（索引元素所指向的数据记录），只有索引，而Ｂ树每个结点中的每个关键字都有卫星数据；这就意味着同样的大小的磁盘页可以容纳更多节点元素，在相同的数据量下，Ｂ＋树更加“矮胖”，ＩＯ操作更少 b+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖”；
（2）、其次，因为卫星数据的不同，导致查询过程也不同；Ｂ树的查找只需找到匹配元素即可，最好情况下查找到根节点，最坏情况下查找到叶子结点，所说性能很不稳定，而Ｂ＋树每次必须查找到叶子结点，性能稳定，
（3）在范围查询方面，B+树的优势更加明显B树的范围查找需要不断依赖中序遍历。首先二分查找到范围下限，在不断通过中序遍历，知道查找到范围的上限即可。整个过程比较耗时。而B+树的范围查找则简单了许多。首先通过二分查找，找到范围下限，然后同过叶子结点的链表顺序遍历，直至找到上限即可，整个过程简单许多，效率也比较高。
使用B+树的好处
由于B+树的内部节点只存放键，不存放值，因此，一次读取，可以在内存页中获取更多的键，有利于更快地缩小查找范围。
B+树的叶节点由一条链相连，因此，当需要进行一次全数据遍历的时候，B+树只需要使用O(logN)时间找到最小的一个节点，然后通过链进行O(N)的顺序遍历即可。而B树则需要对树的每一层进行遍历，这会需要更多的内存置换次数，因此也就需要花费更多的时间
使用B树的好处
B树可以在内部节点同时存储键和值，因此，把频繁访问的数据放在靠近根节点的地方将会大大提高热点数据的查询效率。这种特性使得B树在特定数据重复多次查询的场景中更加高效。
数据库为什么使用B+树而不是B树
因为就是上面提到的B+树的好处。数据库的数据读取都是需要进行代价巨大的磁盘IO操作，因此，更快地缩小范围和更少的读取次数是数据库需要关注的重点。而B+树在这些点上比B树做的更好。这就是为什么数据库要选用B+树作为底层实现。
为什么使用B树查找所用的磁盘IO操作次数比平衡二叉树更少？
答：大规模数据存储中，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的高度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。那么我们就需要减少树的高度以提高查找效率。而平衡多路查找树结构B树就满足这样的要求。B树的各种操作能使B树保持较低的高度，从而达到有效减少磁盘IO操作次数。
参照了一些大哥的博客
/zhoucheng05_13/article/details/79825246
/s/blog_9c581bd30101goui.html
/fct2001140269/article/details/86384197
