树
树状图是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。
子类：二叉树、二叉排序树、平衡二叉树（AVL、红黑树）、B/B+/B*、哈夫曼树
平衡二叉树一定是二叉排序树
红黑树
红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。
左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图3。
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图4。
变色：结点的颜色由红变黑或由黑变红。
B树(B-tree)
B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构
一个节点可以拥有多于2个子节点的二叉查找树
B、B+、B*都是采用二分法和数据平衡策略来提升查找数据的速度；
B+
B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。
B+树的非叶子节点不保存关键字记录的指针，只进行数据索引
B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
非叶子节点的子节点数=关键字数