五、为什么不用红黑树？
红黑树也是BST，但是不是严格平衡的，通过变色和旋转来保持平衡。
必须满足5个约束：
1，节点分为红色或者黑色。
2，根节点必须是黑色的
3，叶子节点都是黑色的NULL节点
4，红色节点的两个子节点都是黑色(不允许两个相邻的红色节点)
5，从任意节点出发，到其每个叶子节点的路径包含相同数量的黑色节点
基于以上规则可以推导出：
从根节点到叶子节点的最长路径（红黑相间的路径）不大于最短路径（全节点的二倍）
为什么不用红黑树？1，只有两路 2，不够平衡
红黑树一般只放在内存里边用，例如：java的TreeMap，它可以用来实现一致性哈希。
六、MySQL中索引的数据结构——B树索引和Hash索引
Hash索引：以KV的形式检索数据，也就是说，它会根据索引字段生成hash码，指针指向数据（memory存储引擎可以使用Hash索引）
Hash索引的优点：(1) 时间复杂度O(1),查询速度比较快，因为Hash索引里边的顺序存储，所以不能用于排序。
(2)查询数据的时候要根据键值计算哈希吗，所以它只能支持等值查询，不支持范围查询，和排序，在有大量重复键值情况下，哈希索引的效率是极低的，因为存在所谓的哈希碰撞问题。
B+树索引
MyISAM: 其中包含三个配置文件 frm 表的结构和定义信息,myd 表的数据,myi 表的索引
MyISAM的B+Tree里边，叶子节点村粗的是数据文件对应额磁盘地址，所以从索引文件.MYI中找到键值后，会到数据文件.MYD中获取相应的数据记录。
非主键索引和主键索引数据的方式是没有任何区别的，一样是在索引文件中找到磁盘地址，然后到数据文件里边获取数据。
InnoDB:
在InnoDB的某个索引的叶子节点上，它直接存储了我们的数据。所以，在InnoDB中索引即数据，就是这个原因。
聚集索引的概念：就是索引键值的逻辑顺序跟表数据行的物理存储顺序是一直的。
InnoDB组织数据的方式就是（聚集）索引组织表(clustered index organize table)。如果一张表创建了主键索引，那么这个主键索引就是聚集索引，决定数据行的物理存储顺序。
InnoDB中，主键索引和辅助索引有主次之分，如果主键有索引，那么主键索引就是聚集索引。其他的索引统一叫做“二级索引”(secondary index)。
二级索引检索数据的流程是这样的：
当我们用Name索引查询一条纪律，它会在二级索引的叶子节点找到了Name=qingshan,拿到了主键值，也就是Id=1，然后再到主键索引的叶子节点拿到数据。为什么不存地址而是存储键值？因为地址会变化。
从这个角度来讲，因为主键索引比二级索引少扫描了一颗B+ Tree（避免了回表，），它的速度会快一点。
七、主键索引的选取与加索引的技巧
主键索引的选取：
1，如果我们定义了主键(Primary key )，那么InnoDB会选择主键作为聚集索引。
2，如果没有显示定义主键，则InnoDB会选择第一个不包含NULL值的唯一索引作为主键索引。
3，如果也没有这样额唯一索引，则InnoDB会选择内置6自己长的RowID作为隐藏的聚集索引，他会随着行记录的写入而主键递增。
加索引的一些技巧：
1，列的离散度，(列的全部不同值)/所有数据的比例 简单的说列的重复值越多，离散度就越低；重复值越少，离散度就越高。 对于离散度高的，即使加了索引，查询消耗的时间更多了，在B+ Tree里边的重复值太多，MySQL的优化器发现走索引跟使用全表扫描差不多的时候，就算建了索引，也不一定会走索引。
对于离散度低的字段，不建议加索引
2，联合索引最左匹配
当我们创建三个字段的索引Index (name,age,address)，相当于创建了三个索引：
Index(a)
Index(a,b)
Index(a,b,c)
3，覆盖索引
回表： 非主键索引先通过索引找到主键索引的值，再通过主键值查询索引里边没有的数据，它比基于主键索引的查询多扫描了一棵索引树，这个过程就叫回表。
在二级索引里边，不管是单列索引还是联合索引，如果select的数据列只用从索引中就能够取得，不必从数据区中读取，这时候使用的索引就叫做覆盖索引，这样就避免了回表。
因为覆盖索引减少了IO次数，减少了数据的访问量，可以大大地提升查询效率。
4，索引条件下推
索引条件下推(Index Condition Pushdown)，5.6以后完善的功能，只适用于二级索引。ICP的目标是减少访问表的完整行的读数量从而减少I/O操作。
将 Index Filter 从 Server 层 Push Down 到了引擎层，减少了因回表产生的磁盘 I/O，也减少了与 Server 层的交互，提高了 SQL 执行效率
举一个例子：
Select * from student where age=22 and name like %明
对于MySQL 5.6之前，能够根据age=22能够查询出数据，name like %明 根据最左匹配原则索引无效，所以查询过程是这样的
（1）根据联合索引查出所有姓名wang的二级索引数据(3个主键值：)
（2）回表，到主键索引上查询所有符合条件的数据
（3）把这三条数据返回server层，在Server层过滤出以zi结尾的员工。
ICP是默认开启的，也就是说针对二级索引，只要能把条件下推给存储引擎，它就会下推，不需要我们干预。