1.3、索引为何不选择红黑树？
上面简单的分析二叉树后，很明显的可以看出，二叉树并不适合作为索引结构，那接下来再看看大名鼎鼎的Red-Black Tree红黑树：
同样提前先构建好了六个节点，相较于之前的二叉树，红黑树则进一步做了优化，它是一种自适应的平衡树，会根据插入的节点数量以及节点信息，自动调整树结构来维持平衡，从树的高度上来看，明显比之前的6层减少到了4层，那此时再来看看检索的过程：
由于树变矮了，其效果也很明显，在红黑树中只需要经过三次查找，就能定位到第五个节点，似乎看起来还不错对嘛？但MySQL为啥不用这颗名声远扬的红黑树呢？
- 红黑树不适合作为索引结构的原因：
- ①虽然对比二叉树来说，树高有所降低，但数据量一大时，依旧会有很大的高度。
- ②每个节点中只存储一个数据，节点之间还是不连续的，依旧无法利用局部性原理。
对于上述两个缺点罗列得很明白，其本质上的原因就在于：单个节点中只能存储一个数据，因此一方面树会随着数据量增长越来越高，第二方面也无法利用局部性原理减少磁盘IO。
那是不是把红黑树稍微改造一下，让其单个节点中可存储多个数据是不是可以了呢？B树就是这样干的，一起来看看。
1.4、索引为何不选择B-Tree？
在前面提到过，将红黑树稍微改造一下，让其单节点可容纳多个数据，就能在很大程度上改善其性能，事实上B-Tree就是这么做的，B树可以理解成红黑树的一个变种，如下：
此时给B树结构也添加了6个节点，此时观测上述结构，一方面树仅有2层，同时一个节点中也存储了多个数据，再来看看B树的查找过程：
哦吼吼吼~，完美完美，两次就查到了数据，同时一个节点中还能存储多个数据，可充分利用局部性原理，让一次磁盘IO读取多个数据！！但有人可能会问，上面的一个节点也只存两个数据啊，没太大的区别似乎。但你要这么想就错了，B树中一个节点可容纳的数据个数，可以自己控制的，例如：
在这里将Max.Degree更改后，B树单节点的容量也会随之更改，从上图中可清晰看到一个节点同时将6个数据全存储进去了，这也就代表着只需要一次磁盘IO就能检索出5这个数据，是不是很完美？先别急着下定律，毕竟咱们目前是站在索引设计者的角度来看待问题的，此时虽然看起来很美好了，但想一个问题：
MySQL由于是关系型数据库，因此经常会碰到范围查询的需求，举例：
SELECT * FROM zz_user WHERE ID BETWEEN 2 AND 5;
比如上述这条SQL语句，需要查询表中ID在2~5的所有数据，那也就代表着需要查四条数据，在这里因为2~5在同一个节点中，因此仅触发一次IO就可拿到数据，但实际业务中往往不会有这么小的范围查询，假设此时是查ID=2~1000之间的数据呢？这么多数据定然不会在一个节点中，因此这里又会触发多次磁盘IO！
- B树不适合作为索引结构的原因：
- 虽然对比之前的红黑树更矮，检索数据更快，也能够充分利用局部性原理减少IO次数，但对于大范围查询的需求，依旧需要通过多次磁盘IO来检索数据。
1.5、索引为何要选择B+Tree？
上面聊到的B-Tree相对来说已经较为完美了，但最后也谈到：它并不适合用于范围查询，但这种查询需求在关系型数据库中又很常见，那这里怎么优化呢？一起来看看B+Tree：
