树

二叉排序树：左节点 < 根节点 < 右节点（节点不相等），左右子树亦是二叉排序树。

红黑树：自平衡二叉查找树。避免二叉排序树的退化，保持平衡的二叉树（目的为降低高度）。                           

退化成链表

B树：多路搜索树 / 平衡多叉树。

B树

索引时，可从磁盘一次加载一个子节点至内存（多路让每个节点数据更少，避免内存不够），使数据分批查找。需要避免根节点的子节点过多，使得B树退化。

退化成数组

B+树：基于B树，数据在统一深度的叶子节点，叶节点链表相连。B+树数据结构与平衡查找树对比形成了三个作用：①数据都在叶子节点，每次查找需要遍历至统一深度，性能稳定；②中间节点不存储数据，整个磁盘页可以存储高度较深的树，减少磁盘IO次数（一页可存储一完整节点）；③叶子节点以链表的形式存储，便于查找。