从B树谈到数据库的索引实现原理
B树（B-tree）：
具有以下性质：
m代表阶数
1、根结点：至少有两个子女
2、非根结点包含的关键字个数为 m/2-1 <= j <= m-1（3： 1<=j<=2）
3、除根以外的内部结点个数 m/2 <= k <= m;
4、根结点在同层
5、每个节点的关键字都是有序的
B+树
与B树的区别在于：
1、每个非叶结点都不保存数据
2、优化后的B+树一般都包含叶子结点之间的指针，极大提高了区间查询效率
3、所有非终端结点都可以看成是索引部分，结点中只包含其子树（根结点）中的最大（最小）值
MySQL索引实现
MyISAM索引实现
叶节点的data域存放的是数据记录的地址，MyISAM的索引文件仅仅保存数据记录的地址
主索引和辅助索引的唯一区别：
主索引要求key是唯一的，而辅助索引的key可以重复
MyISAM中索引检索的算法
首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
InnoDB索引实现
与MyISAM主要区别：
1、InnoDB的数据文件本身就是索引文件
2、叶节点包含了完整的数据记录
3、InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键
4、如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形
5、InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域
6、辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录
下图为主键索引：
辅助索引：