1.Memory用的是hash index，但是InnoDB和MyISAM用的是B+树，不用二叉树的原因就是深度可能过深，深度过深影响查询和IO性能;
2.索引使用树的过程:
BST:二分查找，不平衡
AVL:二叉平衡树,最长子树和最短子树的高度之差不能超过1，数据越多，旋转越多，插入删除效率极低，查询效率比较高，而且树的深度也会比较深
红黑树:最长子树不超过最短子树的两倍即可,通过旋转+变色两步操作，损失了部分查询性能来满足插入性能的提升，但是也存在节点过深，因为只有两个分支;
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
3.InnoDB数据和索引放在 一起 ，MyIsam是分开存放的，所以数据节点的查找方式不一样:
InnoDB:对应叶子节点存储的实际就是一整行的数据，只要遍历到叶子节点就可以取出来整个文件，
但是MyIsam放的是实际文件的地址，通过地址才能找到实际的数据.
索引树一般是3层，mysql的查询是非常快的，但是并发请求和IO会影响查询的性能;
不指定主键最好指定唯一键，唯一键没有会有对用户不可见的row_id;
4.索引的基本知识:
优点:
1>大大减少了服务器需要扫描的数据量;
2>帮助服务器避免排序和临时表->尽量用索引排序
用处:
1>快速查找匹配where子句的行
2>从consideration中消除行，如果可以在多个索引之间进行选择,mysql通常会使用找到最少行的索引
3>如果表具有多列索引，则优化器可以使用索引的任何最左前缀来查找行
4>当有表连接的时候，从其他表检索行数据
5>查找特定索引列的min或max值
6>如果排序或分组时在可用索引的最左前缀上完成的，则对表进行排序和分组;
7>在某些情况下，可以优化查询以检索值而无需查询数据行
5.索引的分类:
数据库会默认建索引，但是给唯一
1>主键索引:唯一且非空索引
2>唯一索引
3>普通索引
4>全文索引
5>组合索引(例如两个name+age组合创建的索引，一般面试会涉及到的技术名词:)
5.1>回表:建索引的时候InnoDB默认情况会为主键创建索引，但是更多情况给普通列创建索引,普通列的索引叶子节点存储的不是整行数据，
那么先查询name的B+索引，然后找到主键的B+索引，拿着主键的B+索引回表查询完整记录;
5.2>覆盖索引:遍历两次B+树，IO次数比较多，回表过程没有了，就是覆盖索引，例如主键idB+树，不需要再select 主键 from ....
举例: select * from emp where name = ‘Tom‘;name做索引的时候它的B+树的叶子节点存储的是主键id，
如果更改为sql语句select id from emp where name=‘Tom‘，此时就不需要再回表查询了，因为上次叶子节点已经查出关于id的信息
5.3>最左匹配:(1)select * from emp where name = ? and age = ?;
(2)select * from emp where age = ?;此时并没有用到(name,age)的组合索引，必须先有左边索引；解决方案换成(age,name)索引或者添加age索引
5.4>索引下推:
(3)select * from emp where name=? 以上(1)(2)(3)3条如何创建组合索引?
方案:A (name,age) ,age 索引
B (age,name)，name索引
索引是需要持久化存储的，所以考虑到age比name的存储较小，使用A解决方案
=>页分裂和页合并的过程
select t1.name,t2.name from t1 join t2 on t1.id=t2.id;(t1 10个列，t2 20个列，最后关联是20个列，或者先取出t1的name和t2的name，
再关联，后者执行效率较高因为范围缩小了)
索引比较好的文章:http://blog.codinglabs.org/articles/theory-of-mysql-index.html
https://www.yuque.com/yinjianwei/vyrvkf/ri4ks7