MySQL技术内幕Charpter5索引
一、B+树
删除填充因子：50%
数据页上存放的是完整的每行记录，索引页上存放的是键值及指向数据页的偏移量
聚集索引的存储在物理上并不是连续的，而是逻辑上连续，页通过双向链表链接，页按照主键的顺序排序；每个页中的记录也是通过双向链表进行维护
二、B+树索引
1.辅助索引
对于辅助索引，叶子节点并不包含行记录的全部数据，每个叶子节点的索引行中还包含一个书签，用于告诉innodb在哪找到与索引相对应的行数据，书签即聚集索引
索引的创建删除可通过：ALTER TABLE 与 CREATE/DROP INDEX
2.
fast index creation
旧版本的index创建时，会使用临时表并迁移数据，完成后在删除没有数据的旧表，对于大表不合适
而FIC在创建index的表上加上S锁，无需重建表，删除辅助索引时只用更新内部视图，并将辅助索引空间标识为可用，同时删除内部视图上对该表的定义
由于创建index时的S锁，故此时只读，当有大量事务对表进行写操作时，同样不可用。且FIC只适合辅助索引，主键的创建与删除还是要重建表。
创建index时会阻塞DML操作，5.6之后支持online DDL，允许辅助索引创建时，还可DML
3.Cardinality
表示索引唯一值的数目的估计值，应尽可能接近1，优化器会根据这个值判断是否使用此索引，但它只是一个大概的值，可以根据ANALYZE TABLE来更新。
如果某个字段取值范围广且几乎没有重复，则属于高选择性，使用B+树最合适。
通过采样进行统计，内部更新cardinality的策略为：1.表中1/16数据发生变化；2.stat_modified_counter>2000 000 000（主要考虑到单行的频繁更新）
默认随机通过8个叶节点进行采样，故几十表结构未变化，cardinality也会变化
三、B+索引的使用
1.不同应用场景
OLTP查询只从数据库中取得小部分数据，B+树建立后，对该索引的使用都是通过该索引取得表中少量数据，此时建立索引才有意义。而OLAP中通常需要获取大量数据，因而索引的添加根据的是宏观的信息，而不是微观，当同时，若OLAP中的复杂查询要涉及多张表的连接，添加索引仍有意义。
2.联合索引
针对select * from table where a =xx and b=xx使用(a,b)联合索引，而对于select * from table where a =xx也可以，但是b不可以使用此B+树。最匹配原则
3.覆盖索引
即从辅助索引中即可获取查询数据，无需聚集索引。优点在于辅助索引不包含整个行记录的所有信息，故大小远小于聚集索引。
统计问题中常用
4.index condition pushdown
数据库在取出索引的同时判断是否进行where的过滤，将where过滤放在了存储引擎层
四、哈希算法
问题：从内存中找到某个被缓存的页，不可能遍历，想到复杂度为O(1)的寻址
针对直接寻址技术存在占用大量空间的问题，使用哈希表，哈希函数数据库中通常采用除法散列
针对哈希冲突的情况，innodb中缓存池内的page页都存在一个chain指针，chain指向有相同哈希函数值的页。对于除法散列，m取值为略大于2倍缓冲池页数量的质数。
对于自然数与page编号的转换，innodb表空间中有一个space_id，用户查询的是某个表空间下连续的页，因而存在一个offset。关键字K=space_id<<20+space_id+offset，然后通过除法散列到各个槽中。
对于字典类型的查找非常迅速，但是对范围查询无能为力。
五、全文检索
B+树支持索引字段的前缀进行查找，如like "xxx%"，但是对内容的查找如like "%xxx%"就力不从心
1.倒排索引
全文索引通常使用倒排索引实现，在辅助表中存储了单词与单词自身在文档中所在位置的映射。
innodb中将(DocumentID,Position)作为一个ilist，而另一个列为word字段，并设有索引
倒排索引将word存放到Auxiliary Table中，后者存在磁盘中。为提高性能使用FTS index cache，其结构为红黑树。
事务提交时将分词写入其中，然后再批量更新到磁盘。对于删除，在事务提交时，不删除Auxiliary Table中记录，而是只删除FTS cache index中记录。即DML并不会实际删除索引中数据，而且还会在DELETE表中插入记录。