什么是索引

　　相当于书目录，用于快速检索

　　优点

　　　　提高数据检索效率

　　　　提高表间的JOIN效率

　　　　利用唯一性索引，保证数据的唯一性

　　　　提高排序和分组效率

　　缺点

　　　　消耗更多物理存储

　　　　数据变更时，索引也需要更新，降低更新效率

　　哪种情况下应该创建索引

　　　　经常检索的列

　　　　经常用于表连接的列

　　　　经常排序/分组的列

　　索引不使用建议

　　　　基数很低的列

　　　　更新频繁但检索不频繁的列

　　　　BLOB/TEXT 等长内容列

　　　　很少用于检索的列

 

二分查找

　　折半查找，binary search

　　一种在有序数组中查找某一特定元素的搜索算法

　　二分查找发的优点是比较次数少，查找速度快，平均性能好，其缺点是要求待查表为有序表，且插入删除困难，因此，二分查找法适用于不经常变动而查询频繁的有序列表

 

二叉树，binary tree

　　二叉树是每个节点至多只有二颗子树（不存在度大于2的节点），二叉树的子树有左右有序之分，次序不能颠倒。

　　

平衡树，平衡二叉树， self-balancing binary search tree

　　改进的二叉查询树。一般的二叉查找树的查询复杂度是跟目标节点到树根的距离（即深度）有关，因此当节点的深度普遍较大时，查询的均摊复杂度会上升，为了更高效的查询，有了平衡树

　　平衡二叉树的特点

　　　　它是一棵空树或其左右两个字数的高度差的绝对值不超过1， 且左右两个子树也是平衡二叉树

　　　　不平衡树会通过自旋，变成平衡树

　　　　平衡树和二叉查找树最大的区别：前者是平衡的，后者未必

 

B树， balanced tree

　　又称 B-树，B_树

　　B树，一个节点可以拥有多于2个子节点的多叉查找树

　　适合大量数据的读写操作，普遍运用在数据库和文件系统

　　一颗m阶（比如m=4阶）的B树满足下列条件：

　　　　树中每个节点至多有m个（4个）子节点

　　　　除了根节点和叶子节点外，其它每个节点至少有m/2个（2个）子节点

　　　　若根节点不说叶子节点，则至少有2个字节带你

　　　　所有叶子节点都出现在同一层，叶子节点不包含任何键值信息

　　　　有k个字节的的非叶子节点恰好包含有k-1个键值（索引节点）

 

B+树， B+TREE

　　B+树是B树的变体，也是多路搜索树，其定义基本与B树相同，除了：

　　　　有n颗子树的节点中含有n-1个关键字（key) ，每个key不保存数据，只用来索引，所有数据都保存在叶子节点

　　　　所有的叶子节点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子节点本身依赖关键字的大小自小而大顺序链接

　　　　所有的非叶子节点可以看成是索引部分，节点中仅含其子树（根节点）中的最大（或最小）关键字

　　　　在MySQL中，为了方便，直接携程BTREE

　　假如有个表，只有一个int列，且设置为主键，无其他更多列

　　　　B+树中，每个非叶子节点开销：6B(row header固定开销) +4B(主键为INT类型) +4B(指向叶子节点的指针开销)

　　　　每行数据开销： 14B + 6B （DB_TRX_ID） + 7B （DB_ROLL_PTR）= 27B

　　　　每个非叶子节点 page 存储约 （16 * 1024-128page header）/ 27 = 600 行记录

　　　　因此，一个三层高的B+树，约可存储记录 1161*1161*600 = 8 亿记录

　　　　

哈希索引，Hash Index

　　建立在哈希表的基础上，它只对使用了索引中的每个值的精确查找有用

　　对于每一行，存储引擎计算出了被索引的哈希码（Hash Code），它是一个较小的值，并且有可能和其他行的哈希码相同

　　把哈希码保存在索引中，并且保存了一个指向哈希表中的每一行的指针

　　也叫散列索引

 

 

B+树索引 VS  哈希索引

　　大量唯一值的等值查询，HASH索引效率通常比 B+TREE高

　　HASH 索引不支持模糊查找

　　HASH 索引不支持联合索引中的最左匹配规则

　　HASH 索引不支持排序

　　HASH 索引不支持范围查询

　　HASH 索引只能显式应用于 HEAP/MEMORY， NDB表

 

聚集索引，clustered index

　　聚集索引是一种索引，该索引中键值的逻辑顺序决定了表数据行的物理顺序

　　每张表只能建一个聚集索引，除了TokuDB引擎

　　InnoDB中，聚集索引即表，表即聚集索引

　　myISAM 没有聚集索引的概念

　　聚集索引优先选择列

　　　　int/bigint　　

　　　　数据连续（单调顺序）递增/自增

　　不建议的聚集索引

　　　　修改频繁的列

　　　　新增数据太过离散随机

 

主键索引，primary key

　　主键由表中的一个或多个列组成，用于唯一地标识表中的某一条记录

　　在表引用中，主键在一个表中引用来自于另外一个表中的特定记录（外键 foreign key应用）

　　保证数据的完整性

　　加快数据的操作速度

　　主键值不能重复，也不能包含NULL

　　主键选择建议

　　　　对业务透明，无意义，免受业务变化的影响

　　　　很少修改和删除

　　　　最好是自增的

　　　　不要具有动态属性，例如随机值

　　InnoDB聚集索引选择次序原则

　　　　显式声明的主键

　　　　第一个NOT NULLABLE的唯一的索引

　　　　DB_ROW_ID (实例级，6 bytes)

　　主键索引一定是聚集索引

　　但聚集索引不一定是主键索引

　　InnoDB表一定有聚集索引

　　InnoDB主键特点

　　　　索引定义时，不管有无显式包含主键，实际都会存储主键值

　　　　在5.6.9后，优化器已能自动识别索引末尾的主键值，在这之前则需要显示加上主键列才可以被识别。

 

唯一索引 unique key

　　不允许具有索引值相同的行，从而禁止重复的索引或键值

　　严格意义上讲，应该叫做唯一约束

　　在唯一约束上，和主键一样 （以MyISAM引擎为代表）

　　其他不同方面

　　　　唯一索引允许有空值（NULL）

　　　　一个表只能有一个主键，但可以有多个唯一索引

　　　　InnoDB表中主键必须是聚集索引，但聚集索引可能不是主键

　　　　唯一索引约束可临时禁用，但主键不行

 

联合索引 combined indexes, multiple-column indexes

　　多列组成，所以也叫多列索引

　　适合where 条件中的多列组合

　　有时候，还可以用于避免回表（覆盖索引）

　　MySQL还不支持多列不同排序规则（MySQL8.0起支持）

　　联合索引建议

　　　　where条件中，经常同时出现的列放在联合索引中

　　　　把选择性（过滤性/基数）大的列放在联合索引的最左边

 

覆盖索引 covering indexes

　　通过索引数据结构，即可之间返回数据，不需要回表

　　执行计划中，extra列会显示关键字 using index

　    回表： 读取的列不在索引中，需要“回到表找到整条记录取出相应的列”

 

前缀索引  prefix indexes

　　部分索引的原因　　

　　　　char/varchar 太长全部做索引的话，效率太差，存在浪费

　　　　或者 blob/text类型不能整列作为索引列，因此需要使用前缀索引

　　部分索引选择建议

　　　　统计平均值

　　　　满足80%-90%覆盖度就够

　　缺点：无法利用前缀索引完成排序

 

InnoDB索引长度

　　索引最大长度767bytes

　　启用innodb_large_prefix,增加到3072bytes，只针对dynamic，compressed格式管用。（8.0默认3072，不需要启用）

　　对于 redundant，compact格式，最大索引长度还是767bytes

　　MyISAM表索引最大长度是1000bytes

　　最大排序长度默认是1024 （max_sort_length）

 

倒序索引

　　8.0开始支持倒序索引

　　联合索引可以使用倒序索引

 

不可见索引

　　优化器不可见。想删除索引时，可以先隐藏索引

 

函数索引、表达式索引

　　8.0.13开始，支持函数索引，表达式索引

　　本质上是 generated column

 

跳跃索引 index skip scan

　　8.0.13开始，支持skip index scan

　　执行计划的extra会显示 using index for skip scan

　　针对单表，不能是多表join

　　sql中不能有group by 或 distinct

　　多列联合索引中，第一列的唯一值很少，且在where条件中未被用到

　　set optimizer_switch=‘skip_scan=off‘; 关闭跳跃索引

 

索引并行读

　　从8.0.14开始，支持主键索引的并行读

　　不支持辅助索引上的并行读

　　使得check table的速度更快

　　新增选项 innodb_parallel_read_threads

　　innodb_parallel_read_threads=4 (默认)，check table耗时减少20%

 

索引管理

　　创建/删除索引

　　　　alter table t add index idx_c1(c1) using btree;

　　　　create index idx_c1 on (c1) using btree;

　　　　create table 时候直接创建

　　　　alter table t drop index idx_c1;

　　　　drop index idx_c1 on t;　　　　

　　冗余索引

　　　　根据最左匹配原则，一个索引是另一个索引的子集

　　　　可以使用工具pt-dumplicate-key-checker检查/schema_redundant_indexex

　　　　重复索引也是冗余的一种，可以直接放心删除

　　　　index k1(a,b,c) , k2 (a,b)  一般认为k2是k1的冗余索引，但是下面sql只有k2才能被使用： where a = ? and b = ? and pk = ?; / where a = ? and b = ? order by pk;

　　　　查看冗余索引： select * from schema_redundant_indexes where table_schema = ‘world‘ \G

　　无用索引

　　　　几乎从未使用过的索引

　　　　pt-index-usage检查低利用率的所有，提供删除建议/schema_unused_indexes

　　　　查看无用索引： select * from schema_unused_indexes where object_schema = ‘world‘; \G

　　查看每个索引利用率

　　　　select index_name,rows_selected,rows_inserted,rows_updated,rows_deleted from schema_index_statistics where table_schema=‘world‘ and tbale_name = ‘city‘;

 

MySQL 索引

标签：类型   特定   set   选择性   mem   针对   ash   没有   二叉树