【有书共读】《MySQL技术内幕》读书笔记05--索引与算法

特点：高扇出性，在数据库中B+树的高度一般在2~4层.

每张表的主键构造成一颗B+树，叶子结点中存放的事整张表的行记录数据
每张表只能有一个聚集索引
聚集索引的存储是逻辑上的连续

辅助索引
叶子节点不包含行记录的全部数据，由键和聚集索引构成叶子节点
查找行记录：通过辅助索引找到聚集索引，在聚集索引B+树上找到行记录
补充：堆表，行数据的插入顺序即为存放顺序，没有聚集索引，通过行号来查找行数据

B+树索引分裂过程
InnoDB存储引擎决定是想做还是向右进行分裂
确定分裂点的位置：如果插入是随机的，那么取页的中间记录为分裂点；否则定位到待插入记录的前一条记录，观察定位的记录之后是否还有3条记录，若有则分裂点为当前向后移动3条，否则分裂点为当前。

创建和删除索引：ALTER TABLE ADD/DROP和CREATE/DROP INDEX
查看索引：SHOW IDNEX FROM TABLE
Fast Index Creation：在辅助索引的创建过程中，对数据表加上Ｓ锁，不能对表进行读操作
Online Schema：在事务的创建过程中，可以有读写事务对表进行操作
MySQL5.6以后支持Online DDL, 包括：辅助索引的创建与删除；改变自增长值；添加或删除外键约束；列重命名

Cardinality值
低选择性：某个字段的取值范围很小，没有必要使用索引
通过SHOW INDEX操作查找cardinality，对选择性进行预估，索引的cardinality/rows值应该尽可能的接近1
更新cardinality值：发生在INSERT和UPDATE操作，通过采样来统计cardinality值。采样过程：对8个叶子节点进行采样，叶子节点的个数为A，统计每个页中不同记录的个数Pi，cardinality=（P1+...+P8）*A/8
更新策略：1.表中1/16数据发生了变化。2.stat_modified_counter>2000000000.

将存储于数据库的整本书或整篇文章的任意内容查找出来，也可以统计和分析
Innodb1.2x,innodb存储引擎开始支持全文检索，支持MyISAM的全部功能。
倒排索引：全文检索使用倒排索引来实现，在辅助表中存储了单词与单词自身在问的那个中位置的映射。1.inverted file index{单词，单词所在文档的ID};2.full inverted index{单词，（单词所在文档ID，在文档中的位置）}。

使用full inverted index倒排索引，（DocumentID, Position）视为ilist，在全文检索的表中，有两列word，ilist。在word上设置索引。
与MyISAM对比：全文索引中没有存放position信息
Auxiliary Table(辅助表)：倒排索引将word存放到一张表中，持久化，存放在磁盘中。
FTS Index Cache(全文检索索引缓存)：红黑树，根据(word,ilist)排序，InnoDB对Auxiliary Table批量更新，合并FTS。
innodb全文索引的限制：1.每张表只能有一个全文检索的索引。2.有多列组合而成的全文检索的索引咧必须使用相同的字符集与排序规则。3.不支持没有单词界定负的语言。

Natural Language
- 默认的全文检索模式，MATCH(col) against （expr）。
- 相关性：word是否在文档中出现，word在文档中出现的次数，word在索引列中的数量，多上个文档包含该word。
- stopword列中的word，不对该词查询。stopword：使用频率高，但是没有意义的单词(如a,the,at...)
IN BOOLEAN MODE全文检索：使用修饰符表示查询条件，+表示word必须存在，-表示必须被排除等
Query Expansion 全文检索的扩展查询：根据搜索的单词进行全文索引，然后根据查询出的粉刺在进行一次全文检索的查询。