本质：数据库维护某种数据结构以某种方式引用（指向）数据
索引取舍原则：索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数
B树 满足的条件d为大于1的一个正整数，称为B-Tree的度
h为一个正整数，称为B-Tree的高度
每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d
每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null
所有叶节点具有相同的深度，等于树高h
key和指针互相间隔，节点两端是指针
一个节点中的key从左到右非递减排列
所有节点组成树结构
每个指针要么为null，要么指向另外一个节点
一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2),检索一个key查找节点的个数的渐进复杂度为logd(N)
更新后的操作插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质
B+树
每个节点的指针上限为2d而不是2d+1
内节点不存储data，只存储key
叶子节点不存储指针
在经典B+树的基础上，增加了顺序访问指针-->提高区间访问的性能
为什么使用B/B+树？ 主存读取当系统需要读取主存时，则将地址信号放到地址总线上传给主存
主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取
主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响
磁盘存取原理磁盘转动，每个磁头不动，负责读取内容
不过已经有了多磁头独立技术
局部性原理
磁盘预读：长度一般以页的整数倍为单位
MyISAM索引实现
使用B+树作为索引结构，data存放数据记录的地址
索引文件与数据文件分离
主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复
非聚集：MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录
.MYI文件的组成整个索引文件的基本信息state
各索引的限制信息base
各索引的定义信息keydef
各索引记录的概要信息recinfo
读取索引的流程query请求，直接读取key cache中的cache block，有就返回
没有就到.MYI文件中以file block方式读取数据
再以相同的格式存取key cache
再将key cache中的数据返回
InnoDB索引实现也是使用B+树
第一个重大区别是InnoDB的数据文件本身就是索引文件，表数据文件本身就是按B+Tree组织的一个索引结构
InnoDB的数据文件本身要按主键聚集
所以InnoDB要求表必须有主键（MyISAM可以没有）
没有显式指定，自动选择唯一标识列
不存在的话，生成6个字节长整型的隐含字段
第二个与MyISAM的不同点InnoDB的辅助索引data域存储相应记录主键的值而不是地址
换句话说，InnoDB的所有辅助索引都引用主键作为data域
辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录
得出的优化点不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大
用非单调的字段作为主键在InnoDB中也不好，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键就很不错了
聚簇索引键被更新造成的成本除了索引数据可能会移动，相关的所有记录数据也要移动
索引使用策略及优化 全列匹配 最左前缀匹配当查询条件精确匹配索引的左边连续一个或几个列时，索引可以被用到
查询条件用到了索引中列的精确匹配，但是中间某个条件未提供只能用到索引中，从中间断开前的列
应对
可以增加辅助索引
当中间条件选项较少时，用隔离列的方式，使用IN包含
看情况，比较建立
查询条件没有指定索引第一列不满足使用索引的条件
匹配某列的前缀字符串可以使用索引
如果通配符%不出现在开头，则可以用到索引，但根据具体情况不同可能只会用其中一个前缀
范围查询范围列可以用到索引（必须是最左前缀），但是范围列后面的列无法用到索引
同时，索引最多用于一个范围列，因此如果查询条件中有两个范围列则无法全用到索引
仅用explain可能无法区分范围索引和多值匹配
查询条件中含有函数/表达式一般不使用哦
手工算好再代入
索引选择性与前缀索引 MyISAM与InnoDB基数统计方式MyisAM索引的基数值（Cardinality，show index 命令可以看见）是精确的，InnoDB则是估计值
MyisAM统计信息是保存磁盘中，在alter表或Analyze table操作更新此信息
而InnoDB则是在表第一次打开的时候估计值保存在缓存区内
不建议建立索引的情况表记录比较少
索引的选择性低：不重复的索引值（也叫基数，Cardinality）与表记录数（#T）的比值
前缀索引