MySQL 数据库存储数据最终是以文件的形式存储到硬盘的，在程序中使用要把磁盘文件中的数据读到内存中
执行一次IO的时间可以执行40万条指令（如果以 CPU 的指令执行效率来比较的话） 数据库量十万百万千万级数据，如每次io 9毫秒的时间显然是个灾难
所以查找数据时把磁盘IO次数控制在一个很小的数量级，一个高度可控的多路搜索树就是 B + 树
树的高度决定着io的次数，如果没有索引 没有索引则检索过程变成了顺序查找，O(n)的时间复杂度几乎是不能忍受 ，每个磁盘块都要发生一次IO(单个磁盘块中不可能存储太多数据) 效率会特别差
一、底层实现原理和优化
在数据结构中，最常见的搜索结构就是二叉搜索树和AVL树(高度平衡的二叉搜索树，，当数据量比较大时，都会由于树的深度过大而造成I/O读写过于频繁，进而导致查询效率低下
mysql的索引数据结构采取的是B+树
B+树索引并不能根据键值找到具体的行数据，B+树索引只能找到行数据锁在的页，然后通过把页读到内存，再在内存中查找到行数据
B+树，它的树高是恒定（可以控制在3到5层），它的渐进复杂度是恒定的
索引若采用哈希：
可以通过hash值定位具体的位置，效率高，但是不能进行模糊查询 范围查询
一个索引的是否优秀判断的依据是 IO渐进复杂度
索引若采用二叉树：
若是一个斜二叉树,查询速度和全表扫描没有区别，树高
索引若采用平衡二叉树：
太深了:深度决定者io的次数,而io耗时大
太小了:结点存储的信息太小了，从而导致频繁的io操作
索引若采用红黑树：
比二叉树相对来说会好一些。它会有一个因子会控制树高，无论二叉搜索树还是AVL树，当数据量比较大时，都会由于树的深度过大而造成I/O读写过于频繁
索引若采用多路平衡二叉树:（B-Tree B树）：
（1）每个节点中有key，也有data，而每一个页的存储空间是有限的，如果data数据较大时就会导致每个节点（即一个页）能存储的key的数量很小
（2）当存储的数据量很大时，同样1会导致B-Tree的深度较大，增加查询时的磁盘I/O次数，进而影响查询效率
B+Tree叶子结点是顺序的,相邻结点存在顺序引用
1:B+Tree拥有B-Tree的优点,深度浅,数据块大
2:因为只在叶子结点存储数据,从而导致扫全表的能力强,因为叶子结点是顺序的,从而导致排序功能更强
二、B+树更适合B树
磁盘读写代价更低：
B+tree的内部结点相对B 树更小，相对来说IO读写次数也就降低了
查询效率更加稳定：
任何关键字的查找必须走一条从根结点到叶子结点的路，所有关键字查询的路径长度相同，导致每一个数据的查询效率相当
主要原因：
B+树只要遍历叶子节点就可以实现整棵树的遍历，而且在数据库中基于范围的查询是非常频繁的，而B树只能中序遍历所有节点，效率太低
三、
原文：https://www.cnblogs.com/webster1/p/12404805.html