最左索引/部分索引 (prefix indexex)

部分索引的原因有:

char/varchar太长全部做索引的话,效率太差

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

例:alert table t1 add index(name(7));//name列上最左边创建7个字符长度

MySQL前缀索引能有效减小索引文件大小,提高索引的速度。

但是前缀索引也有他的坏处:MySQL不能再ORDER BY 或 GROUP BY 中使用前缀索引,也不能把他们用作覆盖索引

#全列选择性

SELECT COUNT(DISTINCT column_name) / COUNT(*) FROM table_name;

#测试某一长度前缀的选择性

SELECT COUNT(DISTINCT LEFT(column_name, prefix_length)) / COUNT(*) FROM table_name;

覆盖索引 covering indexes

覆盖索引又可以称为索引覆盖。

  • 解释一: 就是select的数据列只用从索引中就能够取得,不必从数据表中读取,换句话说查询列要被所使用的索引覆盖。

  • 解释二: 索引是高效找到行的一个方法,当能通过检索索引就可以读取想要的数据,那就不需要再到数据表中读取行了。如果一个索引包含了(或覆盖了)满足查询语句中字段与条件的数据就叫做覆盖索引。

  • 解释三:是非聚集组合索引的一种形式,它包括在查询里的Select、Join和Where子句用到的所有列(即建立索引的字段正好是覆盖查询语句[select子句]与查询条件[Where子句]中所涉及的字段,也即,索引包含了查询正在查找的所有数据)。

索引覆盖举例

  • 索引覆盖是指建索引的字段正好是覆盖查询条件中所涉及的字段,这里需要注意的是,必须是从第一个开始覆盖,比如:

索引字段 条件字段 有没有覆盖
a,b,c a,b 覆盖了
a,b,c b,c 没有被覆盖

第一行满足,第二行不满足

  • 例子: select<字段A,B….> from <数据表 T> where <条件字段C>。在MySQL中建立覆盖索引采用Create index idx on T(C,A,B),建立组合索引时,字段的顺序很重要,要将条件字段C放在组合索引的第一位,把它做为在索引的上层结构的主要排序对象,且仅有它包含统计数据,也就是非子叶层查找出符合的记录,然后在存放有其他字段记录的子叶层读取所需要的数据。

小结

  • 索引覆盖可以大大提高查询速度,在大数据量的时候尤其明显。

联合索引 Combined Indexes,Multiple-Column Indexes

多个列组成一个共同索引,例如 2个列同时作为检索的条件,或者 某一列作为检索条件 另一列用来做排序,这种情况适合创建联合索引 

这样在索引树里就能实现索引的筛选,过滤, 或者左边的部分用来做检索 右边的部分用来做排序 这样效率会比较高 , 而不是创建2个普通的独立索引

建议:把过滤性较好的字段放在前面

MySQL目前还不支持联合索引中的多列使用不同顺序,不能同时使用一种顺序

可以用pt-duplicate-key-checker工具来检查哪些重复索引,一般就是用联合索引取代普通独立索引

对比参考ORACLE索引类型

逻辑上:

  • Single column 单列索引

  • Concatenated 多列索引

  • Unique 唯一索引

  • NonUnique 非唯一索引

  • Function-based 函数索引

  • Domain 域索引

物理上:

  • Partitioned分区索引

  • NonPartitioned非分区索引

  • B-tree:

    • Normal 正常型B树

    • Rever Key 反转型B树

    • Bitmap 位图索引

索引结构:

B-tree:

  • 适合与大量的增,删,改(OLTP)

  • 不能用于包含OR操作符的查询

  • 适合高基数的列(唯一值多)

  • 典型的树状结构

  • 每个节点都是数据块

  • 大多数都是物理上一层,两层或三层不定,逻辑上三层,mysql一般都是3层除非数据量非常大 才会变成四层

  • 叶子块数据是排序的,从左向右递增

  • 在分支块和根块中放的是索引的范围

Bitmap:

  • 适合决策支持系统

  • 做UPDATE代价非常高

  • 非常适合OR操作符的查询

  • 基数比较少的时候才能建位图索引

树形结构:

  • 索引头:

    • 开始ROWID,结束ROWID(先列出索引的最大范围)       

  • BITMAP

    • 每一个BIT对应着一个ROWID,它的值是1还是0,如果是1,表示着BIT对应的ROWID有值

对比一下MySQL的索引基本知识都有哪些

逻辑上:

  • Single column indexes单列索引

  • Combined Indexes, Multiple-Column Indexes多列索引

  • Unique 唯一索引

  • NonUnique非唯一索引

索引结构:

B-Tree:

  • 适合大量的增,删,改(OLTP)

  • 不能用包含OR操作符的查询

  • 适合高基数的列(唯一值多)

  • 典型的树状结构

  • 每个节点都是数据块

  • 大多数都是物理上一层,两层或三层不定,逻辑上三层,mysql一般都是3层除非数据量非常大 才会变成四层

  • 叶子块数据是排序的,从左向右递增

  • 在分支块和根块中放的是索引的范围

hash:

  • 适合小规模数据集快速定位

  • 适合管理内存结构体,LRU链表等

  • 不支持范围查询

  • 不支持模糊搜索

  • 不支持排序

tokudb 可以支持多个聚集索引

MySQL 聚集索引建议

MySQL 尤其是Innodb引擎,是直接把显示定义的主键选为聚集索引的依据, 其他的索引都是非聚集索引

所有的innodb表都要有个聚集索引 为了让检索更高效 锁等待的概率减小 快速定位到某一行 锁的粒度很小 对于数据库并发也很有帮助

根据聚集索引条件 不管是精确定位 还是范围检索 效果都很高 可以直接找到行数据的范围

order by 和 group by的时候只要找到第一条 就可以往下面直接走

因为聚集索引是按照顺序的方式,而且还有整个行的数据,不会导致大量的额外物理IO的产生

我们不应该找一个频繁被修改的列作为聚集索引

频繁删除修改有可能会导致大量空闲空间,碎片产生

PRIMARY KEY, 主键索引

主键的特点

  • 一个表中只能有一个主键,如果在其他字段上建立主键,则原来的主键就会取消

  • 主键的值不可重复,也不能为空(NULL)

在InnoDB中,clustered index选择原则:

  • 显示声明的主键

  • 第一个不包含null列的唯一索引

  • 内置的rowid

InnoDB中,主键特点:

  • 如果索引最后没有主键,则会在索引内部存储时加上主键(只有主键key值,而不是整个row data)

  • 如果索引最后已有主键,则会显式加上主键

  • 因此只要用户定义的索引字段中包含了主键中的字段,那么这个字段就不会再被InnoDB自动加到索引中了,如果用户的索引字段中没有完全包含主键字段,InnoDB就会把剩下的主键字段加到索引末尾

唯一索引(约束)(unique key, UNIQUE Index Constraints)

唯一索引和主键索引的区别

相同点:他们都属于实体完整性约束

不同点:

  1. 唯一性约束所在的列允许空值,但是主键约束所在的列不允空值

  2. 可以把唯一性约束放在一个或多个列上,这些列或列的组合必须是唯一的,但是,唯一性约束所在的列并不是表的主键列

  3. 唯一性约束强制在指定的列上创建一个唯一性索引,在默认情况下,创建唯一性的非聚簇索引,但是也可以指定所创建的索引是聚簇索引

  4. 建立主键的目的是让外键来引用

  5. 一个表最多只有一个主键,但可以有很多唯一键

MySQL 深入理解索引

深入理解索引

  1. 索引基础理论知识

  2. B+树索引

  3. 哈希索引

  4. 理解B+树,哈希索引结构及区别

  5. 理解常见索引的基本概念:主键索引,唯一索引,普通索引,联合索引之间的区别

  6. 理解MyISAM和InnoDB的索引结构区别

  7. 理解如何通过索引提高SQL效率

binary search, 二分查找法,也叫折半查找(折半搜索,二分查找算法,二分搜索),是一种再有序数组中查找某一特定元素的搜索算法。

这种搜索算法每一次比较都使搜索范围减小一般,可在最坏的情况下用0(log n)完成搜索任务。

二分查找法的优点是比较次数少,查找速度块,平均性能好

缺点是要求待查表为有序表,且插入删除困难。

因此,折半查找方法适用于不经常变动而查找频繁的有序列表

binary tree, 二叉树

每个节点至多只有两颗子树(不存在度大于2的节点),二叉树的子树有左右有序之分,次序不能颠倒

平衡二叉树

  1. 左右两个字数的高度差的绝对值不会大过1(<=1),且左右两个子树也是平衡二叉树

  2. 不平衡树会通过自旋,变成平衡树

  3. 平衡树和二叉查找的最大区别:前者是平衡的,后者未必

image.png

旋转后

image.png


image.png

image.png

image.png

用下面这些值来构造一个B树

ACGHEKQMFWLTZDPRXYS

1.构造一个4阶的B树,非根节点关键字数,小于2个就合并,大于4个就分裂

image.png

2.插入H

image.png

3.插入E,K,Q时不需要任何分裂操作,变成:

image.png

4.插入M之后就需要分裂了,M恰好时中间关键字元素,可以放在根节点

image.png

5.插入F,W,L,T不需要任何分裂操作

image.png

6.插入Z时,最右边的叶子节点空间满了,需要进行分裂操作,中间元素T上移到父节点中

image.png

7.插入D时,导致最左边的叶子节点被分裂,D是中间元素,上移到父节点

image.png

8.最后,当插入S时,第三个子节点需要分裂,但根节点已经满了,需要把根节点再次分裂,形成3层的B树

image.png

再来看下元素的删除

1.删除H,节点无需进行合并或分裂

image.png


2.删除T之后,最右边的子节点就没有父节点了,需要再找个新的元素放在其父节点

image.png


3.删除R

image.png

4.删除E之后,第一步变成了

image.png

可以把G,M,Q,X这4个元素提升到根节点,变成了

image.png

B+树是B树(B Tree)的变体,也是一种多路搜索树

  1. 非叶子节点的子树指针与关键字个数相同

  2. 为所有叶子节点增加一个链指针

  3. 所有关键字都在叶子节点出现

二叉树,B树,B+树的小结

Binary树:二叉树,每个节点之存储一个关键字,等于则命中,小于则走左节点,大于走右节点

B树:多路搜索树,没个节点存储M/2到M个关键字,非叶子节点存储指向关键字范围的子节点

所有关键字在整颗树中出现,且只出现一次,非叶子节点可以命中

B+树:在B-树基础上,为叶子节点增加链表指针,所有关键字都在叶子节点中出现,非叶子节点左右叶子节点的索引,B+树总是到叶子节点才命中



经典B+树结构

image.png

==========================================

B+树插入新元素时,可能会遇到3种情况

image.png

image.png

  1. 插入元素28(直接写入 叶子节点没有满)

  2. 插入元素70

    image.png

3.插入元素95

image.png

B+树删除元素时,也可能遇到3中情况

image.png

image.png

  1. 从这个B+树中删除元素70,变成了

image.png

2.再删除元素25,变成了:

image.png

3.再删除元素60,变成了:

image.png

用Innodb的时候一定要注意

  1. 要用顺序自增的主键

  2. 主键可以删除(也不建议)但是一定不要更新它,更新后可能会导致很多碎片产生,建议用字段表示,而不是直接删除,这样高并发下,新增数据性能以及删除数据性能都会比较高,避免频繁合并和分裂

哈希索引

在mysql中,只有memory存储引擎支持显示的哈希索引

关键字key,经过哈希算法hash(key)后,产生一个精确的结果值

image.png

如果有多个关键字相同 产生的hash值也是相同的 有多个重复相同key 会把值放在同一个链表里面,在扫描到这个key的时候就会把链表里的值全部都去取出来

哈希索引和B+树索引的区别:

  1. 先看下逻辑区别

    image.png

索引优点

1.加快数据检索效率

2.可以创建唯一性约束索引,保证数据库中每一行数据的唯一性

3.加速表和表连接效率

4.在使用分组和排序子句进行数据检索时,可以显著减少查询中分组和排序的时间


索引缺点

1.索引需要占用更多物理存储空间

2.当对表中的数据进行增加,删除和修改的时候,索引野要更新维护,降低了数据维护效率


哪些情况下建议创建索引

  1. 经常需要搜索的列

  2. 作为主键的列,有唯一约束索引

  3. 经常用在表连接的列

  4. 经常需要排序的列

  5. 经常使用再where字句中的列

  6. 经常需要排序/分组的列

哪些情况下不建议创建索引

很不经常被搜索的列

基数值很低的列

长text、blob类型列

对比参考ORACLE索引类型

对比一下MySQL的索引基本知识都有哪些

MySQL 聚集索引建议

PRIMARY KEY, 主键索引

唯一索引(约束)(unique key, UNIQUE Index Constraints)

联合索引 Combined Indexes,Multiple-Column Indexes

覆盖索引 covering indexes

最左索引/部分索引 (prefix indexex)

外键/约束(FIREUGN KEY Constraints)

MyISAM主键索引

InnoDB的主键索引和辅助索引

[MySQL FAQ]系列 — 为什么InnoDB表要建议用自增列做主键

[MySQL优化案例]系列 — InnoDB主键设计

MySQL 第三方引擎应用场景分析

Infobright是开源的MySQL数据仓库解决方案,引入了列存储方案,高强度的数据压缩优化的统计计算(类似sum/avg/group by之类),列式存储 对单列处理效率非常高 如果涉及到多列相对较慢。

Infobright的默认存储引擎是brighthouse,但是Infobright还可以支持其他的存储引擎,比如MyISAM,MRG_MyISAM, Memory,CSV

企业版增加了DML支持,同时有一些额外的工具集

社区版不支持DML,没有在线热备工具

Infobright优点

  1. 高压缩比率,平均压缩比可达10:1,甚至可以达到40:1。

  2. 列存储,及时数据量十分巨大,查询速度也很快。用于数据仓库,处理海量数据没一套可不行。

  3. 不需要建索引,就避免了维护索引及索引随着数据膨胀的问题。把每列数据分块压缩存放,每块有知识网格节点记录块内的统计信息,代替索引,加速搜索。

  4. 单一台服务器可以高效的读写30T数据。具有可扩展性,这里是指对于同样的查询,当数据量是10T时,它耗费的时间不应该比1T数据时慢太多,基本是一个数量级内。

缺点:

  1. 不支持DML

  2. 不支持多核

  3. 不支持分布式

image.png

loader与unloader是infobright的数据导入导出模块,也即处理SQL语句里LOAD DATA INFILE ··· 与 SELECT “` INTO FILE任务,由于infobright面向的是海量数据环境

所以这个数据导入导出模块是一个独立的服务,并非直接使用muysql的模块

逻辑层的infobright优化器包再mysql查询优化器的外面,因为它的存储层有一些特殊结构,所以查询优化方式也跟mysql有很大差异

存储层最底层是一个个的Data Pack(数据块)。每一个pack装着某一列的64K个元素,所有数据按照这样的形式打包存储,每一个数据块进行类型相关的压缩(即根据不同类型采用不同的压缩算法),压缩比很高。它上层的压缩器与解压缩器就做了这个事情。

Knowledge Grid(知识网格)中包含两类节点:

  • 每个Data Pack Node(数据包节点)对应一个Data Pack,存储改Data Pack的一些统计信息,如min,max,avg,null个数,单元总数count,sum总数等,甚至不同值的量等等;

  • KN(Knowledge Node,知识节点)则存储了一些更高级的统计信息以及与其他表的连接信息,这里面的信息有些事是数据载入时已经算好的,有些事随着查询进行而计算的,所以说是具备一定的“智能”的

KN里面存储着指向DP之间或者列之间关系的一些元数据集合,比如值发生的范围(Min_Max),列数据之间的关联。大部分的KN数据是装载数据的时候产生的,另外一些是查询的时候产生。

image.png

Histogram用来提高数字类型(比如data,time,decimal)的查询性能。Histogram是装载数据的时候就产生的。

DPN中有mix,max,Histogram中把Min-Max分成1024段,如果Min_Max范围小于1024的话,每一段就是一个单独的值。

这个时候KN就是一个数值是否在当前段的二进制表示。

image.png

CMAP是针对于文本类型的查询,也是装载数据的时候就产生的。CMAP是统计当前DP内,ASCII在1-64位置出现的情况。如下图所示

image.png

比如说上面的图说明了A再文本的第二个,第三个,第四个位置从来没有出现过。0表示没有出现,1表示出现过。

查询中文本的比较归根究底还是按照字节进行比较,所以根据CMAP能狗很好的提高文本查询的性能。

Pack-To-Pack(P-2-P)是join操作的时候产生的,它是表示join的两个DP中操作的两个列之间关系的位图,也就是二进制表示的矩阵。

image.png

这个sql在innodb里跑了2.96秒

infobright vs innodb

0.29s vs 2.96s