MySQL 数据结构用 b+tree 做的

为什么不用红黑树叉树呢？

不用红黑树是因为，一个节点就是一个数据，那么比如每读取一个节点就是一次 i/o 读写，大量的 i/o 读写会造成效率低下；

也会消耗大量的内存。

什么是 B-Tree（B-树）？

B树是为了磁盘或其他存储设备而设计的一种多路平滑查找树。

与红黑树很相似，但在降低磁盘 I/O 操作方面要更好一些。

许多数据库系统的索引一般都采用 B-Tree 或者 B-Tree 的各种结构作为底层数据结构。

什么是 B+Tree？

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，MySAM和InnoDB存储引擎底层就是用B+Tree实现其索引结构。

B+Tree 相对于 B-Tree 的几点不同

1、非叶子节点只存储键值信息。
2、所有叶子节点之间都有一个链指针。
3、数据记录都存放在叶子节点中。