为什么会使用B-Tree和B+Tree，而不是二叉树、红黑树
数据结构
说索引之前需要先提到一点，树结构做查找时，最坏情况需要查找的次数是树的高度H，而对于Mysql来说，当数据文件很大时，就需要根据树的节点把对应的数据加载到内存中，也就是I/O。
上面的描述中有几点信息：
- 树高H影响查找次数；
- 上一点中的每一次查找还会涉及到磁盘I/O;
记 N 为 B-tree 中的 Key 的数据量，d 为内节点出度的二分之一，则我们可以证明
，渐进复杂度为
。
d 为内节点出度，表示非根节点和叶子节点拥有最少的子女数，并且规定最大不能超过 2d。注意：这里也有文献会反过来表示，即最大为 d, 最少不能少于
很明显，树高度H越高查询效率越低。
回到问题上，我相信很多人已经猜到了为什么B树会比二叉树更合理了！但是这只是说明了一个层面的东西，高度越低查询次数越少。
局部性原理与磁盘预读
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：
每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。
B-Tree 和 B+Tree 区别
最大上的不同是内节点不存储数据。
另外，每个节点的指针数不一样，B-Tree 是数据隔开指针，上文提到过最大子女数是 2d，所以B-Tree的最大指针数是 2d+1；而B+Tree 是 2d。
Mysql不同索引实现
通过上文两点，我们理解了为什么使用B树。但同样是B树，也有不同的使用。
聚集和非聚集
聚集与非聚集的主要区别可理解为索引的叶子节点中存储是真实的数据还只是指针。这一点，在MyISAM和InnoDB的主键之间表现是不同的。MyISAM使用的是非聚集，最好的表现在MyISAM的存储文件分为索引文件(.MYI)和数据文件(.MYD)，而InnoDB是索引和数据在一个文件里。
上文可理解MyISAM和InnoDB区别之：
- 存储的文件内容不一样；
- 因为InnoDB是根据主键聚集数据的，所以在创建InnoDB表时必需要有主键；
- 扩展一点：InnoDB辅助索引是根据主键值聚集的；什么意思？就是InnoDB的非主键索引的叶子节点里存储的是主键的值；
