常用结构对比

二叉树

缺点

在数据库的使用中，更多的场景是自增 id，在连续自增插入的情况下，二叉树单边插入，退化成链表，此时的时间复杂度变为 O(N)，性能严重下降。

红黑树

优点

红黑树是平衡二叉树的一种，是二叉树的升级版，在添加或删除节点时会自动保持平衡，保证任意一条路径的长度不超过其他路径的 2 倍，保证了在查找、插入和删除的时间复杂度稳定在 O(logN)。

缺点

1. 为了保持平衡，在数据量大之后，节点的旋转操作引发多层级节点变动，影响插入、删除性能。
2. 数据量大之后，树的高度也会随之增高很多，给查询性能带来一定影响

B-Tree

优点

1. 节点横向存储的数据量更多，随着数据量增多，节点反转次数小于二叉树。
2. 横向存储数据更多之后，高度相对于二叉树有所降低，减少磁盘 IO 次数，有更高的查询性能。

缺点

1. B-tree 中的节点既可以是叶子节点又可以是非叶子节点，这样不如 B+tree 可以把叶子节点连成链表，提高范围遍历的效率。
2. 所有节点都是既存索引又存数据，这样在遍历查找时，磁盘 IO 次数较多，不利于查询。

B+Tree

优点

1. 非叶子节点只存索引不存储数据，这样可以使单个页存储更多的数据，横向存储数据变多，树的高度降低，减少了 IO 次数
2. 叶子节点包含所有元素，组成双向链表，便于范围查找

特点

1. 聚簇索引的叶子节点存储的是完整数据，非聚簇索引叶子节点存储的是主键id+索引数据，所以在查询时尽量只查用到的字段，如果字段都在索引中，那直接查索引就行，不需要回表。

其他知识点

页结点大小？

可以用这个命令查询，默认是 16 KB

select @@innodb_page_size / 1024 as page_size

高度为 3 的 tree 最多可以放多少数据？（聚簇索引）

主键用 bigint，占用 8 Byte

磁盘文件索引地址占用 6 Byte

所以一个非叶子节点的占用为：索引 + 磁盘索引地址 = 14 Byte

每个页按 16 kb 来算，每页存储的索引数量为：16 kb / 14 Byte ≈ 1170 个

叶子结点我们按每个元素是 1 kb 计算，这样每页可以放 16 个结点

最终高度为 3 的树，最多可以放 1170 * 1170 * 16 ≈ 2200 万 个索引数据