内存中的索引通常采用BST、红黑树，外存中通常采用B树、B+树
BST对于检索来说，有个大的缺点是它不一定平衡。如果对于一个已排序的数列建BST，BST会退化成一个斜着的链表。为了解决“平衡”的问题，比较常见的有AVL树和红黑树。
红黑树 即是一棵 平衡的 扩充 二叉搜索树
颜色特征：结点 红 或
黑；根和扩充的外部空叶结点都是黑色
内部特征：红 结点的两个子节点都是
黑 的，不允许连续的 红 结点
深度特征：任何结点到其叶子结点的每条简单路径都包含相同数目的
黑 结点
阶为k的红黑树路径长度 最短是k ，最长是2k （阶 :
黑色高度）
黑色 起到一个阶的控制作用
插入算法
· 先调用BST的插入算法
- 把新纪录着色为 红
- 若父结点是黑色，则算法结束
· 否则，双红调整
插入算法调整1：重构
· 情况1：新增结点 X 的 叔叔 是 黑色
以祖父结点为轴旋转父结点
插入算法调整2：换色
· 情况2：新增结点X的 叔叔 也是 红色
父祖换色