1. 红黑树
红黑树是一种平衡二叉树，相比起AVL树，红黑树在树的平衡上放松了一些约束，实际上也没有必要达到AVL树这么严格的平衡度，这会导致每次插入或删除都需要旋转一些次数才能维护。红黑树主要有以下五个性质：
(1) 每个节点要么是红色，要么是黑色
(2) 根节点是黑色
(3) 叶节点是黑色
(4) 红色节点的子节点是黑色
(5) 任意一节点到叶节点每条路径的黑色节点数一样
维护这五个性质，可以证明对红黑树的插入，删除，查询等操作的期望时间复杂度是$O(\log n)$的。红黑树在维护性质上主要依靠三种基本操作，分别是左旋，右旋和变色。
2. B-树（B树）
B-树是B树不是B减树，B-树和B树是同一个东西。与平衡二叉树不同，B-树可以看作是平衡多叉树。B-树有这些性质：
(1) 根节点的子节点数为$[2,m]$
(2) 非根非叶节点的子节点数为$[m/2,m]$
(3) 每个叶节点的高度一致
(4) 每个节点键的个数等于其子节点数减一
B-树使用键来划分数据，大于第1个键的数据划分到第一棵子树，在第1个键和第2个键之间的数据划分到第二棵子树，大于最后一个键的数据划分到最后一棵子树。B-树和B+树的一个不同，就是B-树的键上是有数据的，在查询时，当直接命中键就可以直接返回。B-树在插入时，如果遇到子节点数大于等于$m$时，则将该节点分裂成两个节点，每个节点取一半的子树，并利用这些子树确定键。在删除时，如果遇到子节点数小于$m/2$时，可以从兄弟节点借一棵子树；如果不存在可以借的子树，则和兄弟节点合并。通过上述步骤不断往根节点递归调整，就可以在每次插入或删除后维护B-树的性质了。
3. B+树
B+树在B-树的基础上做了一些修改，主要有这些性质：
(1) 根节点的子节点数为$[2,m]$
(2) 非根非叶节点的子节点数为$[m/2,m]$
(3) 每个叶节点的高度一致
(4) 每个节点键的格式等于其子节点数
(5) 叶节点有一条链连接
B+树比起B树最大的区别就是B+树所有的数据都存储在叶节点，非叶节点全部看作索引，即使非叶节点的值等于查找值，也要到叶节点才能取得数据。这么做的好处首先是B+树的非叶节点只需要存储索引值而不需要存储整个数据，其次查找效率稳定。非叶节点只需要存储索引值，大大节省了B+树的存储空间；查找效率稳定是指无论查找哪个数所需要的时间都是差不多的。B+树的性质(4)使得在合并或分裂节点时更简单，直接进行合并或分裂就可以了，无需再维护键值，这说明B+树在处理性质时比B-树更简单，效率也更高。性质(5)使得B+树可以在命中区域周围继续搜索，完成区域查找。