分类： MYSQL

覆盖索引 covering indexes

leokim / / MYSQL

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

  • 解释一： 就是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

leokim / / MYSQL

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

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

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

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

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

对比参考ORACLE索引类型

leokim / / MYSQL

逻辑上：

  • 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的索引基本知识都有哪些

leokim / / MYSQL

逻辑上：

  • Single column indexes单列索引

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

  • Unique 唯一索引

  • NonUnique非唯一索引

索引结构：

B-Tree：

  • 适合大量的增，删，改（OLTP）

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

  • 适合高基数的列（唯一值多）

  • 典型的树状结构

  • 每个节点都是数据块

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

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

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

hash：

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

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

  • 不支持范围查询

  • 不支持模糊搜索

  • 不支持排序

tokudb 可以支持多个聚集索引

MySQL 聚集索引建议

leokim / / MYSQL

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

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

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

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

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

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

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

PRIMARY KEY， 主键索引

leokim / / MYSQL

主键的特点

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

  • 主键的值不可重复，也不能为空（NULL）

在InnoDB中，clustered index选择原则：

  • 显示声明的主键

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

  • 内置的rowid

InnoDB中，主键特点：

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

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

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

唯一索引（约束）（unique key, UNIQUE Index Constraints）

leokim / / MYSQL

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

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

不同点：

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

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

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

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

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

MySQL 深入理解索引

leokim / / 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 第三方引擎应用场景分析

leokim / / 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