树型结构由于其良好的递归特性， 高效的查询效率， 在软件系统设计中有着非常广泛的使用。 IO多路复用的epoll实现采用红黑树组织和管理sockfd， 以支持快速的增删改查； Golang中的Timer采用多叉堆实现； Java中的TreeMap以及TreeSet同样采用红黑树实现…而在MySQL中， 索引的构建同样采用树结构实现。
1. 什么是B-Tree
B-Tree简单的来讲就是一颗矮胖的多叉平衡树， 通常不会超过3层。
如上图所示， 每一层均由指针， 索引值以及卫星数据组成。 进行搜索时， 同样采用二分查找的方式进行搜索， 所以搜索效率与树的高度直接相关， 这也是为什么B-Tree的树高非常少的原因， 其目的就在于提高搜索效率。
那么既然降低树高能够提高搜索效率， 为什么不干脆使用有序列表呢?
现在树高只有1， 搜索的平均时间复杂度即为O(logn)， 不是比B-Tree更快吗？ 有一个很关键的点就是， B-Tree是为了构建存储数据的索引而生， 数据量庞大且将会被持久化至磁盘或者SSD上。 如果说某一张表拥有过亿的数据量， 且服务器只有4G的内存， 根本无法将列表形式的索引完全载入内存， 二分查找也就无从说起。
2. 为硬盘存储而生的B-Tree
已经9102年了， 服务器使用HDD作为持久层已经成为了一个过去式， 目前均采用SSD， 即固态硬盘作为持久层， 其读写效率约为HDD的10倍左右。
SSD简单的来看是由很多个Block(块)组成， 而Block又由很多个Page(页)所组成。 Page的大小通常为4K或者是8K， Blcok的大小通常为512K。
由于SSD没有向磁盘一样的悬臂， 所以不需要磁头的机械运动， 在读取数据时， 只需要找到数据所在的Block即可。 由于SSD特殊的组成方式， 在进行数据读取时， 其最小单位为Page， 也就是一次最小读取为4K或者是8K。 而对于删除数据来说， 其最小单位为Block， 因为需要进行加压擦除。
B-Tree之所以适合作为数据库索引结构的存储， 就是因为其矮胖的树型结构。 如果我们将索引树改为红黑树或者是AVL树这种二叉树的话， 会发生什么？
假设树高为4， 所需的数据刚好位于AVL树的叶子节点， 那么在最坏的情况下(数据分散在不同的Page中)， 想要取出这条数据， 就需要4次的IO操作。 而IO操作， 相较于CPU的计算， 可以说慢如龟爬。 随着层高的增加， IO次数随线性增长， 这是我们不能接受的。
而对于B-Tree来讲， 就不会存在这样的问题， 因为其树高也就只有3、4层， 无论数据位于叶子节点还是非叶子节点， 其IO次数最多也只是4次而已。
3. B+Tree
B+Tree是B-Tree的进化版， 目的在于进一步减少磁盘IO次数， 提供稳定的查询效率以及优化范围查找。
首先来看B+Tree的基本结构， 与B-Tree最大的不同就是: B+Tree的所有数据均保存在叶子节点， 非叶子节点只保存指针以及索引值。
如上图所示， 所有的数据均保存在B+Tree的叶子节点， 非叶子节点不保存数据， 这样一来使得在4K/Page的容量限制下， 能够保存更多的索引数量。 运气好的话原来使用B-Tree需要4层树高， 使用B+Tree的话可能只需要3层树高， 磁盘IO次数进一步降低了。
并且由于B+Tree只在叶子节点保存数据， 所以每一次查询都需要遍历至树底， 而所有叶子节点均处于同一层， 所以所有的查询时间复杂度都是相同的。
除此之外， 在叶子节点所有的数据均使用指针进行相连接， 也就是一个有序链表， 在进行范围查找时拥有极高的效率。 并不需要像B-Tree一样进行前序或者后序遍历。
4. 哈希索引
其实到这里有关B-Tree和B+Tree的内容就结束了， 但是还是忍不住再BB两句。
Hash Table是一种以空间换时间的数据结构， 底层由数组实现， 其平均查询时间复杂度为O(1)。 而B+Tree的平均查询时间复杂度为O(logn)， 那么索引为什么不使用哈希表， 而要使用B+Tree呢？
因为在数据库查询这一场景， 取出单一的一条数据这种需求占比并不会特别大， 更多的是使用某一种规则取出符合该规则的多条数据。 如果只是单一的一条数据， 那么哈希索引的效率确实要优于B+Tree。 但如果取出多条数据， 或者对数据进行排序的话， 那么B+Tree为更好的选择。
MySQL的InnoDB存储引擎只允许用户定义B+Tree索引， 不允许用户定义哈希索引， 就是因为无法判断用户是否能正确使用哈希索引。 但是InnoDB会根据实际情况自动地为某些数据添加哈希索引， 以增加查询速度。
5. 小结
从B-Tree以及B+Tree的使用场景上来看， 没有适用于一切场景的数据结构， 只有最适合某些场景的数据结构。 在学习数据结构的过程中， 有时候不仅要关注它的原理， 更需要关注它的设计初衷以及适用场景。