平衡二叉树、红黑树、B+树比较
平衡二叉树
性质：
- 每个节点最多有2个子节点
- 左右子树高度差不超过1
- 当前节点值大于左孩子，小于右孩子
缺陷：每次插入、删除都需要大量的左旋右旋操作
红黑树
红黑树弥补了平衡二叉树插入删除的问题
性质：
- 根节点为黑色
- 红节点的子节点必为黑色
- 从根节点到任意一个节点，包含相同数目的黑色节点
STL中红黑树（map, set）的迭代器实现：
- 第一个节点是树中最小的节点
- 如果存在右子树，则下一个节点是右子树的最小节点
- 如果不存在右子树，则向上寻找。找到一个节点其右节点未被遍历过，则这个节点是下一个节点，找不到意味着完成遍历
整体过程类似中序遍历
B树与B+树
B树是一种多路查找树，节点中有多个key，表示子节点值的区间。插入与删除时，会改变节点中key的数目
B+树：
- 只有叶子节点包含数据
- 每个非叶子节点的key数目相同，插入删除时不改变非叶子节点数目
- 叶子节点用一个链表串起来，方便快速遍历
与红黑树比较：B树/B+树时多叉的，查询时间复杂度都为O(logn)，不过当数据块在磁盘上时，B+树的磁盘IO数目更少，应为用链表串起来了