InnoDB中的索引:

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

B+树的演变

演化过程：

数组—>二叉查找树(BST)—>均衡二叉树(AVL)—>B-树—>B+树
程序查找二分左右深度差<=1m叉树，叶子在同一层数据全保留在叶子，叶子之间有指针
注：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');