MySQL为什么使用B+树而不是B-树？
2020-05-15 本文已影响0人
飞跑的蛤蟆
B-树、B+树、红黑树都是平衡查找树，从查询效率上讲，平均都是O(log n)。
但为什么MySQL使用B+树，而不是B-树呢？
首先来看下，MySQL作为关系型数据库该如何衡量查询效率呢？--磁盘IO次数
关系数据库这种数据量大索引能达到亿级别，为了减少内存的占用，索引也会被存储在磁盘上。B-树/B+树的特点就是每层节点数目非常多，层数少，目的就是为了减少磁盘的IO次数，但是B-树的每个节点都有data域（指针），这无疑是增大了节点大小，也增加了磁盘的IO次数（因为磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就会减少，IO次数也会增多），而B+树除了叶子节点其他节点并不存储数据，节点小，磁盘IO次数就少。
- B+树只有叶子节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有Data域
- B+树所有的Data域在叶子节点，并且所有叶子节点之间都有一个链指针。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问了。在数据库中基于范围的查询时非常频繁的，而B树不支持这样的遍历操作。
