AVL树

概念：AVL树称为平衡二叉树，对于平衡二叉树，他的每个节点的左子树和右子树之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间旋转，将二叉树维持在一个平衡态。

红黑树

红黑树的特点：
1.每一个节点不是红色就是黑色
2.跟总是黑色的
3.如果节点是红色的，那么它的子节点必须是黑色的（反之并不一定必须为真）
4.从根节点到叶子节点的每条路径，必须包含相同数目的黑色节点
红黑树比AVL树的优势在哪里
首先红黑树是不符合AVL树的平衡条件的；但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候选择次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。红黑树的插入效率更高。

B树

特征：
1.任意非叶子节点节点最多只有M个儿子
2.跟节点的儿子树为[2,M]
3.除根节点以外的叶子节点的儿子树为[M/2,M],向上取整
4.非叶子节点的关键个数=儿子树-1
5.所有叶子节点位于同一层
6.k个关键字把节点拆成k+1段，分别指向k+1个儿子，同时满足查找树的大小关系。
特性：
1.关键字集合分布在整颗树中；
2.任何一个关键字出现且只出现在一个结点中；
3.搜索有可能在非叶子结点结束；
4.其搜索性能等价于在关键字全集内做一次二分查找；

B+树

1.含有K个关键字元素的非叶子节点有k颗子树，这些关键字不保存数据，只用来索引，所有数据都保持在叶子节点中（而b树是每个关键字都保持数据）
2.所有的叶子节点包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序连接。
3.所有的非叶子节点可以看成索引部分，节点中仅含其子树的最大关键字。
4.通常在B+树上有两个头指针，一个指向跟节点，一个指向关键字小的叶子节点。
5.同一个数字会在不同节点中重复出现，根节点的最大元素就是b+树的最大元素。

B+树应用在MyISAM和InnoDB中

B+树应用在MyISAM（非聚簇索引）

1.主键索引
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的原理图：

image.png

MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

B+树应用在InnoDB（聚簇索引）

MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

image.png

(图inndb主键索引）是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引

关于MyISAM和InnoDB中主键索引和辅助索引

一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。

二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。

参考：
https://blog.csdn.net/mmshixing/article/details/51692892
https://blog.csdn.net/yyc1023/article/details/53925246
https://blog.csdn.net/bitboss/article/details/53219945
https://blog.csdn.net/login_sonata/article/details/75268075