公众号内回复：面试宝典，可获得《面试通关宝典》一部
一般来说索引非常大，尤其是关系型数据库这种数据量大的索引能达到亿级，所以为了减少内存的占用，索引也被存储在磁盘上。B-树和B+树的特点就是每层节点数目非常多，层数很少，目的就是为了减少磁盘IO次数，但是B-树的每个节点都是Data域，所以每个节点很大，而且增加了磁盘IO次数（磁盘IO每次读出来的数据量大小都是固定的，单个数据变大，每次读出的比之前少，IO次数增多），而B+树除了叶子节点，其他节点并不存储数据，节点小，磁盘IO次数就变少。
b-树和红黑树基本都是存储在内存中才会使用的数据结构。大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下的情况。
通过以上的描述，磁盘IO次数等同于树的高度，B+tree树的高度比红黑树矮，所以它就成为实现索引的 不二选择。同时，B+树只要遍历叶子节点就可以实现整棵树的遍历，而且在数据库中基于范围的查询是非常频繁的，而B-树只能中序遍历所有节点，效率太低。
但是，hash数据结构也很快啊，为什么不使用它呢？虽然hash可以快速定位，但是没有顺序，不支持多条查询，IO复杂度高；还有二叉树的树高度不均匀，不能自平衡，树的高度随着数据量增加而增加，IO代价也随之增高。
为什么官方建议使用自增长主键作为索引？
结合B+树的特点，自增主键是连续的，在插入过程中尽量减少页分裂，即使要进行页分裂，也只会分裂很少一部分。并且能减少数据的移动，每次插入都是插入到最后（减少分裂和数据移动的频率）
参考：
https://www.e-learn.cn/content/mysql/2048850
https://my.oschina.net/lienson/blog/2987474
如果觉得文章不错，可以扫描下方二维码进行关注。
