今天我们来说说几种不同的树的数据结构

二叉排序树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
二叉排序树的定义：
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
1.若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2.若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3.左、右子树也分别为二叉排序树；
简单点说，左边比跟节点小，右边比根节点大。并且左右子树都是二叉排序树。
如果二叉排序树是平衡的，则n个节点的二叉排序树的高度为Log2n+1,其查找效率为O(Log2n)，近似于折半查找。

但是二叉排序树会出现一种极端的情况，当存储的数据是有序的序列的时候，比如：4,5,6,7。所有的值都会集中到左侧，退化成一个链表。如下图：
这种情况下查询的时间复杂度就变成了O(n)

二叉平衡树

二叉树的查找速度取决于树的高度n，高度越低查询速度越快，为了做到降低树的高度，就需要让树尽可能的平行，左右子树的数量尽量保持一致。
红黑树作为二叉平衡树中的一种，其结构如下图：
综上所述，二叉排序树的查找性能在O(Log2n)到O(n)之间。

B树

定义如下：
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
1.根结点至少有两个子女；
2.每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；
3.除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；
4.所有的叶子结点都位于同一层。
简单点说，B树是一种平衡的多叉树，它的每个节点可以拥有多于两个孩子的节点，M路的B树最多能拥有M个孩子节点。
上图为一颗三路B树，每个节点最多可拥有两个孩子
设计成多路的结果也是为了降低树的高度，但是过多的路也会导致B树退化成一个有序数据。
B树的使用场景：文件系统和数据库的索引都是存储在磁盘上，如果数据量大的话，不能将整颗树的数据全部一次的加载到内存中。如果是B树，每次只需加载一个节点的数据到内存中，然后逐步查找就可以少量的内存空间查找到目标数据。

B+树

如上图，是一个4路B+树，它的数据都在叶子节点，与B树不同的是每个数据都有链表相连。MYSQL的数据库索引就使用B+树来存储。
为什么不用二叉排序树、红黑树或B树来作为存储索引的数据结构呢？这个也和使用场景有关系，我们知道B树适用于文件系统，因为减少数据加载到内存中的数据量，每次只需要加载一个节点的数据就可以。而数据库的SELECT查询操作，更多的时候需要查询多条数据且需要做排序。如果使用B树的话，获取到所有的数据就需要做中序遍历，而B+树的所有数据都在叶子节点上，叶子节点又是链表结构，只需要找到首尾，就可以查询到所需的数据。