数据结构

二叉树

比上个节点小的数据会放在树的左边，大的会放在树的右边

当树比较平衡时，查询会比链表快

问题：

处理自增，有序的数据可能会退化为链表，这样查询速度没有提升

红黑树（二叉平衡树）

在二叉树的基础上进行了升级，可以对树进行平衡，通过修改根节点的方式，防止树退化为链表。

当树的一边比另外一边高2层就会自动平衡。

问题：

数据量大的时候，会导致数据层级太高。

如果找到的数据时层级很深的叶子节点，也会循环很多次，效率也就不高了。

B Tree

在红黑树的基础上进行了升级，通过扩展叶子节点，来解决红黑树层级过高的问题。

让一个节点可以存储多个数据，同时一个节点可以指向多个不同的叶子节点。

这时，每个叶子节点与非叶子节点上都存有数据key与data。

问题：

每个节点都存储有数据的key与data，占用着磁盘空间。

如果数据的data很大，则会挤压key的空间，这样节点存储的数据量就会少。

在数据量很大时，也会有层级深度较大的问题。

每次遍历节点都需要与磁盘交互，层级深度会增大查询时磁盘I/O交互，进而影响查询效率。

B+ Tree

B+ Tree 是在 B Tree的基础上进行的一种优化。

在非叶子节点只存储key，通过key找到叶子中的data，这样非叶子节点可以存储大量的key。

叶子节点存储数据的key与data，通过指针让它们形成一个有序的列表，这让范围查找更加便捷。

在MySQL的InnoDB存储引擎就使用的B+ Tree结构，并对其进行了一定的优化。