MySql索引与B树

InnoDB 中的索引:

• B+ 树索引
• 全文 (Full Text) 索引  不反对中文
• 哈希索引

这里的哈希索引是自适应的（主动实现的），innodb 会主动依据状况生成 hash 索引，不能人为干涉。
B+ 树的 B 代表 balance 而不是 binary，B+ 树不属于二叉树。B+ 树常利用于磁盘存储中。

B+ 树的演变

演化过程：

注：b- 树（均衡多路查找树）又称 B 树

B- 树与 AVL 的区别：

• 变成了 m 叉树，使得关键字增多，从而树的深度缩小
• 所有叶子节点在同一层，且都为 NULL
• m 个关键字的节点至多有 ⌈ m/2⌉个子树。

关键字更多。档次更少，查找更快。

B+ 树与 B - 树的区别:

• B+ 树的分枝节点不再保留关键字指针，只保留索引。
• 叶子节点保留了所有关键字信息。（数据，指针都保留在叶子节点）
• 叶子节点之间有 双向指针 相连。
• 同一节点中的数据按值从小到大排序。
• n 个关键字的父节点有 n 个字树。

档次更少。查问更稳固（每次都一样）。遍历更快（叶子之间有指针）

B+ 树的三个操作：插入

• 插入

注：旋转，用于缩小拆页次数。

• 删除

依据 删除后的 填充因子来判断是否删除，50% 是能够设置的最小值。

第一种状况：都没小于填充因子 50%

第四种状况：索引节点的填充因子 < 50% && 叶子节点不小于。

注：这种情况表中没有列出来，然而下图就是这种。该书的作者此处有笔误。

第三种状况

扇 (shan) 出：一个模块调用其余模块的格数。扇入：被多少个模块调用。

B+ 树索引

汇集索引(clustered index)、辅助索引(secondery index)

• 汇集索引
  为每张表的主键结构一颗 B + 树(叶子按程序寄存)，叶子节点寄存表的行记录数据，叶子节点 == 数据页。数据页之间双向指针连贯。一张表只能有一个汇集索引。

  范畴查找 十分快。（因为有程序，而且有双向指针）
  汇集索引的字段必须是 NOT NULL && UNIQUE

• 辅助索引
  叶子节点不蕴含所有行记录数据，每个叶子节点还蕴含一个书签(bookmark)，书签指向的就是汇集索引。

创立索引的语法

创立

• ALTER TABLE tbl_name
ADD [idx_type] | [idx_name] (clo1,col2...)

  idx_type 蕴含（unique,primary key,fulltext,index）

删除

• ALTER TABLE tbl_name
DROP PRIMARY KEY
| DROP {INDEX|KEY} idx_name

创立 局部索引(不是整个数据，而是结尾的肯定长度)

• ALTER TABLE tbl_name
ADD KEYidx_b (b(100))

这里 b 字段为 varchar(8000)，但只建设前 100 个字符。
查看索引:SHOW INDEX FROM tbl_name;
更新基数 Cardinality：ANALYZE TABLE tbl_name;

基数 Cardinality

示意索引中 不重复记录数 的 预估值 。
理论利用中，Cardinality 应尽可能靠近 1。如果值十分小，也示意没必要创立该索引。
什么时候创立索引
当列的值各种各样时，能够思考创索引，如 name 字段。
对于值比拟繁多的列，无需创索引。如：sex 字段值只有 M /F。

B+ 树索引应用

联结索引、笼罩索引

• 联结索引

  对于索引 idx_a_b(a,b)，存储构造也是一个 B + 树，只是每个节点有多个值（这里为 2）:
  
  对于 where a=xxx and b=xxx;  idx_a_b 无效。
  对于 where a=xxx;   idx_a_b 无效。
  但对于 where b=xxx;   idx_a_b 就生效了。

  因为 (1,2)(1,2)(2,1)(2,4)(3,1)(3,2) 对于第一个字段 a 是有序的；对于 a 雷同时，b 也是有序；但值看 b，则没有程序了。这就是 前缀匹配。

  联结索引的 长处 ：会对前面的字段排序。
  实用场景 ：查找同一用户，按工夫排序的购物记录。
  增加索引: ALTER TABLE tbl_name ADD INDEX idx_uid_buydate(uid,buydate);

• 笼罩索引

  指从辅助索引中查到记录，而不需去汇集索引中查，效率更高。

  因为辅助索引只间接保留了一部分数据，所以构造会比拟小，能更快查出来。
  应用场景：统计函数 COUNT(*)会先走笼罩索引。

强制应用索引 force index(idx_name):select * from table_name force index (index_name) where conditions;
索引提醒 use index(idx_name): 通知优化器，能够考虑一下这个索引来查，决定权在优化器自身。

优化器不应用索引：
典型场景：查整行 select * 时，辅助索引扫描 (index scan) 不会应用，因为查整行还要通过书签去汇集索引查，所以优化器就间接应用了汇集索引进行全表扫描(table scan)。

MRR 优化 (Multi-Range Read)
实用于：range,ref,eq_ref。有索引进行 范畴 查找时会进一步优化。
命令:SET @@optimizer_switch = 'mrr=on,mrr_cost_based=off'; 总是开启 mrr，不思考代价。
应用提醒 extra: using mrr;

ICP 优化 (Index Condition Pushdown)
实用于:range,ref,eq_ref,ref_or_null。对 where 条件进一步优化。
如对于索引 (a,b,c),where a=”123″ and b LIKE “%xx%” and c LIKE “%yy%”;
本来索引 b 会生效 (LIKE 加 % 结尾)，但 ICP 优化器会进一步优化，进一步过滤。
应用提醒:using index condition;

全文检索(Full-Text-Search)

定义：用于检索整本书或整篇文章中 任意内容 的技术。
全文索引应用 倒排索引 (inverted index) 来实现，inverted index 保留着{单词, 文档 id，文档中的地位}

• InnoDB 全文检索

  采纳 full inverted index 实现，存储着{word,(DocumentId,Position)},word 又独自存在一个辅助表中。

  每张表只能有一个全文检索的索引。
  全文索引中各列的字符集和编码要雷同。
  不反对没有界定符号（如空格）的语言：中文，韩语等。

  应用命令 WHERE MATCH(col) AGAINST(‘key’)：SELELCT * FROM tbl WHERE MATCH(col) AGAINST('key');