二叉树：
自平衡树：为了解决二叉查找树退化成链表的问题，具有二叉树全部特性。每个节点的左子树和右子树的高度差至多等于1。
缺点：每次进行插入/删除节点的时候，几乎都需要通过左旋和右旋来调整至平衡状态，在插入/删除很频繁的场景中，性能低下
红黑树（自平衡二叉树）：
B树：子树越多表示数的高度越低，搜索效率越高；可以在文件查找的时候每次只加载一个磁盘页的内容存入内存来查找。而红黑树在内存中查找非常块，但是如果在数据库和文件系统中，显然B树更优
B+树：与B树相比，数据都存在叶子节点，各叶子节点通过指针，形成链表
B*树：在B+树的非根和非叶子结点再增加指向兄弟的指针
为什么B+树用于数据库中的索引呢？
因为在数据库中select常常不只是查询一条记录，常常要查询多条记录。比如：按照id的排序的后10条。如果是多条的话，B树需要做中序遍历，可能要跨层访问。而B+树由于所有数据都在叶子结点，不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能够把所有数据取出来了。
