B Tree和B+Tree

1、为什么使用B Tree

常用的查找类数据结构做下对比：

哈希表：定位速度快，时间复杂度为O(1)，但是不支持范围查询

二叉树：支持定位和范围查询，但是可能失衡

二叉树失衡

红黑树：虽然做了数据平衡，但是数据量大的时候深度会比较大，磁盘I/O会很频繁，导致查询效率低

B Tree：是为了磁盘存储结构设计的多路平衡树，在同样的数据量下，B Tree的树深度低，磁盘I/O读写次数少，达到性能的提升

2、B Tree为什么能提升查询性能：

下图显示了B Tree中1~26主键索引的数据结构，指针指向磁盘块地址，数据是该主键对应表那一行的数据。使用的是聚簇索引，什么是聚簇索引，可以参考下一篇文章，会介绍索引。

B Tree主键存储示例

下图红黑树中1~15主键的存储结构：

红黑树主键存储示例

假设要查找id=15的数据，B Tree会将根节点磁盘块1常驻内存，发现比9大比18小，根据指针找到磁盘块3，然后将磁盘块3所有数据加载到内存，再从中查找id=15的数据。只用了一次磁盘I/O。

再看红黑树中，将根节点4常驻内存，比较id=15，比4大，将右节点8加载到内存，比较后再加载右节点10到内存...一直找到15为止，一共进行了5次磁盘I/O才找到id=15的数据。红黑树要频繁读取数据结构中存储的节点，为什么不是直接将以8下面的整块右子树加载到内存？因为子节点不像B Tree一样是存储在相同的磁盘块中的，数据是分散到不同盘面的不同扇区上，即使将8下面的整个右子树一次性读取，实际上还是要频繁读取磁盘中的节点才能加载到内存。

3、B+Tree的优势

mysql的MyISAM和InnoDB存储引擎底层使用的是B+Tree，B+Tree是在B Tree基础上优化的。

B+Tree模拟主键索引示例

1、B+Tree的非叶子节点只存储键值信息，只有叶子节点才存储数据，在同样磁盘块大小下可以存储更多键值对，可以降低树的深度，从而减少磁盘I/O

2、叶子节点存储了所有的数据，并且通过指针连接到下一个磁盘块数据，不需要借助父节点，范围查找效率更高