BST 二叉搜索树
特殊的二叉树，节点值>左孩子，节点值<右孩子。查找时间复杂度O(logN)等价于进行一次二分搜索，特殊情况下会退化至O(n)。
AVL 平衡二叉搜索树
查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(log n）
BST的变种，所有结点的左子树和右子树高度差不超过1，需要严格保持平衡。当插入和删除操作破坏平衡后，通过旋转来保持平衡。
插入分为 ll、rr、lr、rl四种情况。后两种情况要比前两种多旋转一次。
红黑树
在O(log n)时间内完成查找、插入和删除。
相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体性能优于AVL树
红黑树的特点：
- 节点是红色或者黑色
- 根节点时黑色
- 所有的叶子节点是黑色（叶子是NIL节点 空）
- 每个红色节点的孩子节点必须是黑色（不可以有两个连着的红色节点）
- 从任一节点到其叶子节点的路径都包含固定数量的黑色节点。
B树（B-树、B_树）
自平衡的多阶查找树
B树特点：
- 根节点含有零个或两个孩子节点
- 其他非叶子节点含k个孩子节点（m/2<k≤m）
- 含有k个子节点的节点拥有k-1个键。
在操作系统中，数据以页的形式被加载入内存，对于树的查找，每一次比较就要加载新的页进入内存，B树相较于红黑树更加矮胖，可以减少IO次数，而IO属于比较耗时的操作，所以，B树适合用来读写相对大的数据块的存储系统，常被应用在数据库和文件系统的实现上。
B+树
B树的变种，B+ 树能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。
B+树特点：
- 非叶子节点不保存数据，所有数据都保存在叶子节点
- 根节点有0或者2个孩子节点
- 非页非根节点拥有k个孩子节点，就拥有k个键值。根节点的最大值是整颗树的最大值。
- 叶子节点间有指针相连，头尾分别有头指针和尾指针
相较于B树，因为数据都在叶子节点中，所以B+树的查找效率更加稳定。B+树和B树的节点含有相同数量的键值时，B+树中的孩子节点多一，所以B+树更加矮胖，IO次数更少。由于叶子节点中存在指针，做范围查询、排序等操作更加便捷。同时，操作系统加载数据时，会进行预加载，把相邻的页加载入内存呢，因为存在指针的存在，更方便