MySQL InnoDB 二级索引的排序

排序问题

最近看了极客时间上 《MySQL实战45讲》,纠正了一直以来对 InnoDB 二级索引的一个理解不到位,正好把相关内容总结下。PS:本文的所有测试基于 MySQL 8.0.13 。

先把问题抛出来,下面的 SQL 所创建的表,有两个查询语句,哪个索引是非必须的?

CREATE TABLE `geek` (
  `a` int(11) NOT NULL,
  `b` int(11) NOT NULL,
  `c` int(11) NOT NULL,
  `d` int(11) NOT NULL,
  PRIMARY KEY (`a`,`b`),
  KEY `c` (`c`),
  KEY `ca` (`c`,`a`),
  KEY `cb` (`c`,`b`)
) ENGINE=InnoDB;

select * from geek where c=N order by a limit 1;
select * from geek where c=N order by b limit 1;

作者给的答案是索引 c 和 ca 的数据模型是一样的,因此 ca 是多余的。为啥??

我们知道,二级索引里存放的不是行的位置,而是主键的值,也知道索引是有序的。

如果 c 与 ca 的数据模型一样,那么就要求二级索引的叶子节点不仅是按索引列排序、而且还按关联的主键值进行排序

我以前的理解是 二级索引只按索引列进行排序,主键值是不排序的。

问了专栏作者,得到的答复是:索引 c 就是按照 cab 这样排序,(二级索引))有保证主键算进去、还是有序的。(PS:非原话,前后问了三次得到)。

本着 先问是不是,再问为什么 的思路,进行一番探究。

继续阅读

《数据库索引设计与优化》笔记二

第八章 为表连接设计索引

基本问题BQ:是否存在或者计划设计一个索引,使它包含所有被 where 子句引用的列。BQ 背后的原理是:保证只有知道 是必须被访问的表行时,才去访问该表。

基本连接问题 BJQ:是否有一个已经存在或计划添加的索引,包含了所有本地谓词对应的列?在表连接中指包含了涉及的所有表的本地谓词。

合并扫描连接和哈希连接

合并扫描连接执行过程如下:

  • 执行表或索引扫描以找出满足本地谓词的所有行。
  • 随后可能会进行排序,如果这些扫描未按所要求的顺序提供结果集。
  • 对前两步生成的结果集进行合并。

在以下情况中,合并扫描连接会比嵌套循环连接快:

  • 用于连接的字段上没有可用的索引。这种情况下,使用嵌套循环,内层表可能需要被扫描很多次。
  • 结果表很大。这种情况下使用嵌套循环会导致相同的页被不断重复访问。
  • 连接查询中不止一张表的本地谓词的过滤因子很低。嵌套循环可能导致对内层表(或者内层表索引)的大量随机访问。

继续阅读

《数据库索引设计与优化》笔记一

第二章 表和索引结构

B-Tree-index

索引页和表页

目前页的大小一般是 32K64K 的。页的大小决定了一个页可以存储多少个索引行、表行,以及一共需要多少个页来存储表或者索引。每个页都会预留一定比例的空闲空间,以满足向其添加新的行。缓冲池和 I/O 活动都是基于页的

索引行

对于唯一索引,一个索引行等同于叶子页中的一个索引条目。字段值没表中复制到索引上,并加上一个指向表中记录的指针。

对于非唯一索引,一个索引值后带着多个指针,指针指向下一层非叶子页或叶子页,叶子页的指针指向表中的记录。

B 树索引结构

非叶子页包含着一个键值,以及一个指向下一层级页的指针,该键值是下一层级页中的最大键值。多个索引层级按照这一方式逐层建立,直到根页。

(对于非唯一索引)通过这种方式来查找任何一条索引记录都需要访问相同数量的非叶子页。

第三章 SQL 处理过程

谓词是索引设计的主要入手点。

第四章 为 select 语句创建理想的索引

三星索引评定:

  • 第一颗星:与查询相关的索引行是相邻的,或者至少相距足够靠近。最小化了必须扫描的索引片的宽度。
  • 第二颗星:索引行的顺序与查询语句的需求一致。排除了排序操作。
  • 第三颗星:索引行包含查询语句中的所有列。避免了回表。

宽索引:款索引是指一个至少满足了第三颗星的索引。该索引包含了 select 语句所涉及的所有列,因此能够使得查询只需访问索引而无须回表。

继续阅读

MySQL 高性能的索引策略

重新看了一遍做得记录。

独立的列

索引列不能是表达式的一部分,也不能是函数的参数。在 where 语句里,始终将索引列单独放在比较符号的一侧。

前缀索引和索引的选择性

选择性是指不重复的索引值和数据表的记录总数的比值。
选择性越高查询效率越高,唯一索引的选择性是 1。

对于很长的索引列,判断它的前缀是否有足够的选择性。
MySQL 无法用前缀索引做 order bygroup by ,也无法用前缀索引做覆盖扫描。

多列索引

MySQL 5.0 引入索引合并策略。索引合并使用的范围: OR 条件的联合,AND 条件的相交,组合前两种条件的组合和相交。
索引合并暗示着不良的设计,可以考虑组合索引。

索引列顺序

正确的顺序依赖于使用该索引的查询,并且同时需要考虑如何更好地满足排序和分组的需要。

将选择性高的列放在最前列,通常不如避免随机 I/O 和排序重要。
不需要考虑排序、分组时,应将选择性最高的列放在最前面。

性能不只是依赖于所有索引的列的选择性,也和查询条件的具体值有关,也就是和值的分布有关。

继续阅读

《高性能 MySQL》 — 第五章 创建高性能的索引

索引基础

索引的使用:现在索引中找到对应值,然后根据匹配的索引记录找到对应的数据行。

对于有多列的索引,MySQL 只能高效地使用索引的最左前缀列。因此列的顺序很重要。

MySQL 的唯一限制和主键限制都是通过索引实现。

索引的类型

MySQL 中,索引是在存储引擎层而不是服务器层实现的,所以没有统一的索引标准。

B-Tree 索引

B-Tree 通常意味着所有的值都是按顺序存储的,并且每一个叶子页到根的距离相等,适合范围查询。

btree-structure

B-Tree 索引适用于全键值、键值范围或键前缀查找,其中键前缀查找只适用于根据最左前缀的查找。

索引还可以用于查询中的 order by 操作。

B-Tree 索引的限制:

  • 如果不是安装索引的最左列开始查找,则无法使用索引。
  • 不能跳过索引中的列。
  • 如果查询中有某个列的范围查询,则其右边所有列都无法使用索引优化查找。

这些限制是 MySQL 优化器和存储引擎使用索引的方式导致的。

继续阅读

Oracle B-Tree 索引的结构、特点及索引扫描方式

《Oracle DBA 手记 — 数据库诊断案例与性能优化实践》摘录(P218)

Oracle 数据库中索引的存储结构使用的是 B Tree 的一种变体,称为 B*Tree (B Star Tree),在数据库中存储数据以块为单位。
Oracle B-Tree索引结构

一些术语:

  • 节点 M 的深度:从树根节点到节点 M 的最短路径长度。图中根节点 Root 的深度是 0,节点 L1-1 的深度是 1,节点 L0-1 的深度是 2。
  • 节点 M 的层数:节点 M 的层数与其深度是相同的。
  • 树的高度:树的深度值最大的那个节点,其深度 +1 即为树的高度。图中树的高度为 3。

继续阅读

Oracle 索引分区

摘录自《 ORACLE数据存储与访问技术》

从物理上说,索引是组织索引键值及其行地址的存储手段,是一个具有两字段的特殊表。

Oracle 支持表分区和索引分区的独立设计,即支持 “表不分区-索引不分区、 表分区-索引不分区、 表分区-索引分区、 表不分区-索引分区” 四种组合。

Oracle 支持 本地分区索引 和 全局分区索引。

本地分区索引(local partitioning index)

本地分区索引是指索引的分区方法与对应表的分区方法相同,表的每个分区有自己对应的索引段,创建时用 local 指定索引属性。

本地分区索引的优点:

  1. 取决于分区条件和查询条件的组合,Oracle 能够应用分区裁剪(partition pruning)功能定向到分区索引的特定分区,减小了索引树的规模。
  2. 分区表在分区的维护过程中,如对表的某个分区执行删除(drop)、截断(truncate)、合并(merge)等操作,Oracle 自动对与之关联的本地前缀索引执行相同的操作,且索引始终保持有效的状态,不需要对整个索引进行重建(rebuild)。
  • 本地前缀分区索引(local prefixed partitioning index):本地前缀分区索引是指表分区键是索引键的前导列。

  • 本地非前缀分区索引(local nonprefixed partitioning index):索引键的前导列不是分区键。

继续阅读

《Oracle数据库性能优化》笔记 – 索引与 bitmap 索引

需要复杂技巧及高深知识来解决所遇到的问题的情形并不多,相对来说,在对基本概念有清晰认识的情形下,解决问题的切入口通常都会比较准确。

索引的作用

索引是以最快的路径找到所需要的数据;另一个功用是对数据完整性的强制控制。

在下面两种情形下,系统会自动为表的列建立索引:

  1. 当表的列被指定为 primary key 时;
  2. 当表的列有 unique constraint 时。

当一个表中有 foreign key 存在时,通常也建议这个列使用索引。

索引管理的常见问题

  1. 最近是否做过数据库的分析
  2. 索引的数量,过多或过少都是不好的

索引不被使用的情况

  • 当对同一个表的两个列进行比较的情形下,索引有时不会被使用。

  • null 值。如果 where 语句中出现 is null 或者 is not null 时,索引就不能被使用。

  • 当 where 语句中存在有 not function 时,比如 not in, not exist, column <> value, column > value, column2 < value 等情形下,索引不能被使用。

  • 当 select 语句使用了 single-row function时,如 nvl, to_char, lower 等,索引不能被使用。

  • 通配符 % 或者 _ 作为查询字符串的第一个字符时,索引页无法使用。如果查询字符串的第一个字确定,则可以使用索引。

继续阅读