原文：https://segmentfault.com/a/1190000019419783
作者：SkinnyTracy
定义：索引是帮助MYSQL高效排好序的资料结构
索引储存在档案里
形式：二叉树 HASH BTREE
为什么用BTREE而不用二叉树：
如果每次的资料都是以1,2,3,4,5,6的形式新增，会造成二叉树单边增长，从而导致查询效率依然低下
红黑树会自己旋转，会有一个自平衡的过程，但是高度是不可控的,（height）,如果是百万级别的资料，高度是完全不可控的
为什么用BTREE而不用HASH：HASH如果是单个查询条件会比较快，比如col=3,直接用hash(index=3)即可，但是范围查询的话效率很慢，大部分公司有很多业务都会是范围查询
如果让你来设计MySQL的BTREE，你觉得degree设为多少合适？
设为磁盘I/O一个节点的值，假如一次I/O最多取4k,就设为4k，作均衡
B+TREE的优势：非叶子节点不储存资料，只储存key
评价一个索引结构好坏的标准:磁盘I/O次数
预读：磁盘一般会顺序向后读取一定长度的资料（页的整倍数）放入内存
区域性性原理:如果一个数据被用到了，那他附近的资料也马上会被用到
B+TREE的度一般会超过100，所以高度h会非常小(一般在3-5之间）
MyISAM索引实现:MyISAM索引档案和资料档案是分离的 储存引擎是表级别，不是数据库级别
D-->Data I-->index
InnoDB-->聚集索引-->资料和索引是放在一起的-->是按主键索引构建的一个BTREE树
InnoDB-->推荐使用整型自增主键-->保证资料可以顺序插入到当前索引节点的后续位置，如果是用UUID，需要比较ASCII码，还有可能插入的地方空间不足需要分裂开，花费更多的时间
不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大
为什么非主键索引结构叶子节点储存的是主键值？(一致性和节省储存空间)
