在关系数据库中,索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储数据结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。
索引的作用相当于图书的目录,可以根据目录中的页码快速查找到所需的内容。
在 MySQL 中,存储引擎用类似的方法使用索引,先在索引中找到对应值,然后根据匹配的索引记录找到对应的行。
首先说明下 MySQL 的索引主要是基于 Hash 表或者 B + 树。
了解索引就需要从索引常见的数据结构开始了解学习,这里有集中常见的的索引数据结构。
二叉树是每个节点最多只有两个分支(即不存在分支度大于 2 的节点)的树结构。通常被称之为 “左子树” 和 “右子树”
左子树 < 父节点 <= 右子树
二叉树的第 i 层至多有有 2^(i-1) 个节点,
深度为 K 的二叉树至多总共有个 2^k-1 节点(定义根节点所在深度 k0=0),而总计拥有节点数符合的,称为 “满二叉树”;
二叉树通常作为数据结构应用,典型用法是对节点定义一个标记函数,将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉搜索树和二叉堆,并应用于高效率的搜索和排序。
同时学习数据结构,这里还推荐 Data Structure Visualizations 进行学习,可以非常直观的看到数据结构允许的过程,一步一步的怎么走的都可以很清晰看得到。
找到其中的 Binary Search Trees 二叉树。
可以直观的看到二叉树的数据插入过程,如下:
可以看到二叉树不适合用作当作索引的,数据量庞大的话,二叉树的层数会很大,查找效率固然也很慢了。 推荐阅读:维基百科 - 二叉树
是一种自平衡二叉查找树,典型用途是实现关联数组。
红黑树的结构复杂,但它的操作有着良好的最坏情况运行时间,并且在实践中高效:它可以在 O (log n) 时间内完成查找,插入和删除,这里的 n 是树中元素的数目。
红黑树遵行以下原则:
下面是一个具体的红黑树的图例:
这些约束确保了红黑树的关键特性:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。
要知道为什么这些性质确保了这个结果,注意到性质 4 导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。因为根据性质 5 所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。
同样在 Data Structure Visualizations 中选择 Red-Black Trees 红黑树进行插入操作可以直观的看到红黑树的插入过程:
同样红黑树也不适用于 MySQL 的索引,数据量庞大之后,数层也会变大。
推荐阅读:
由于无法装入内存,则必然依赖磁盘(或 SSD)存储。而内存的读写速度是磁盘的成千上万倍(与具体实现有关),因此,核心问题是 “如何减少磁盘读写次数”。
首先不考虑页表机制,假设每次读、写都直接穿透到磁盘,那么:
BST
):读 / 写平均 O (log2 (n)) 次;如果树不平衡,则最差读 / 写 O (n) 次
AVL
):在 BST 的基础上加入了自平衡算法,读 / 写最大 O (log2 (n)) 次
RBT
):另一种自平衡的查找树,读 / 写最大 O (log2 (n)) 次
BST
、AVL
、RBT
很好的将读写次数从 O (n) 优化到 O (log2 (n));其中,AVL
和 RBT
都比 BST
多了自平衡的功能,将读写次数降到最大 O (log2 (n))。
假设使用自增主键,则主键本身是有序的,树结构的读写次数能够优化到树高,树高越低读写次数越少;自平衡保证了树结构的稳定。如果想进一步优化,可以引入 B树
和 B+树
。
又称:多路平衡查找树。大多数存储引擎都支持 B 树索引。b 树通常意味着所有的值都是按顺序存储的,并且每一个叶子节点到根的距离相同。B 树索引能够加快访问数据的速度,因为存储引擎不再需要进行全表扫描来获取数据。下图就是一颗简单的 B 树。
在 B 树中,内部(非叶子)节点可以拥有可变数量的子节点(数量范围预先定义好)。当数据被插入或从一个节点中移除,它的子节点数量发生变化。为了维持在预先设定的数量范围内,内部节点可能会被合并或者分离。
如下图所示:
只演示了插入的过程,其中可以通过 delete、find 执行删除和查找操作。直观的感受到 B 树的执行过程。
每个节点存储了多个 Key 和子树,子树与 Key 按顺序排列。
同二叉搜索树类似,每个节点存储了多个 key 和子树,子树与 key 按顺序排列。
页表的目录是扩展外存 + 加速磁盘读写,一个页(Page)通常 4K(等于磁盘数据块 block 的大小,见 inode 与 block 的分析),操作系统每次以页为单位将内容从磁盘加载到内存(以摊分寻道成本),修改页后,再择期将该页写回磁盘。考虑到页表的良好性质,可以使每个节点的大小约等于一个页(使 m 非常大),这每次加载的一个页就能完整覆盖一个节点,以便选择下一层子树;对子树同理。对于页表来说,AVL(或 RBT)相当于 1 个 key+2 个子树的 B 树,由于逻辑上相邻的节点,物理上通常不相邻,因此,读入一个 4k 页,页面内绝大部分空间都将是无效数据。
假设 key、子树节点指针均占用 4B,则 B 树节点最大 m * (4 + 4) = 8m B;页面大小 4KB。则 m = 4 * 1024 / 8m = 512,一个 512 叉的 B 树,1000w 的数据,深度最大 log(512/2)(10^7) = 3.02 ~= 4。对比二叉树如 AVL 的深度为 log(2)(10^7) = 23.25 ~= 24,相差了 5 倍以上。震惊!B 树索引深度竟然如此!
那为什么 B 数这么厉害了,还有 B + 树的出现呢,必然是解决 B 树存在的问题
1、为定位行数
2、无法处理范围查询
数据表的记录有多个字段,仅仅定位到主键是不够的,还需要定位到数据行。有 3 个方案解决:
方案 1 直接 pass,存储数据行将减少页面中的子树个数,m 减小树高增大。
方案 2 的节点中增加了一个字段,假设是 4B 的指针,则新的 m = 4 * 1024 / 12m = 341.33 ~= 341,深度最大 log(341/2)(10^7) = 3.14 ~= 4。
方案 3 的节点 m 与深度不变,但时间复杂度变为稳定的 O (logm (n))。
个人认为优先选择的方案 3 。
实际业务中,范围查询的频率非常高,B 树只能定位到一个索引位置(可能对应多行),很难处理范围查询。改动较小的是 2 个方案:
乍一看感觉方案 1 比方案 2 好 —— 时间复杂度和常数项都一样,方案 1 还不需要改动。但是别忘了局部性原理,不管节点中存储的是数据行还是数据行位置,方案 2 的好处在于,依然可以利用页表和缓存预读下一节点的信息。而方案 1 则面临节点逻辑相邻、物理分离的缺点。
推荐阅读:
主要变动如上所述:
回顾上一个 B 树,一个 m 阶的 B 树具有如下几个特征:
1、根结点至少有两个子女。
2、每个中间节点都包含 k-1 个元素和 k 个孩子,其中 m/2 <= k <= m。
3、每一个叶子节点都包含 k-1 个元素,其中 m/2 <= k <= m。
4、所有的叶子结点都位于同一层。
5、每个节点中的元素从小到大排列,节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域分划。
一个 m 阶的 B + 树具有如下几个特征:
1、有 k 个子树的中间节点包含有 k 个元素(B 树中是 k-1 个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。
2、所有的叶子结点包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
3、所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。
B + 树是 B 树的升级版,其有如下特性:
同样在 Data Structure Visualizations 中选择 B+ TreesB + 树
进行插入操作可以直观的看到插入过程
在动图中可以看出,B + 树的每一个叶子节点都有一个指针指向下一个节点,把所有的叶子节点串在一起。索引数据都存储在叶子节点中。
B + 树相比于 B 树,有什么优势呢:
1、单一节点存储更多的元素,使得查询的 IO 次数更少。
2、所有查询都要查找到叶子节点,查询性能稳定。
3、所有叶子节点形成有序链表,便于范围查询。
总结,B + 树相比 B 树的优势有三:1.IO 次数更少;2. 查询性能稳定;3. 范围查询简便。
推荐阅读:
hash 索引基于 hash 表实现,Hash 索引是将索引键通过 Hash 运算之后,将 Hash 运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中。
只有精准匹配索引所有列的查询才有效。索引的检索可以一次定位,不像 B-Tree 索引需要从根节点出发到目标节点。虽然 Hash 索引很快,远高于 B-tree 索引,但是也有其弊端。
通过 navicat 工具查看表设计选项中,从引擎中可以看到 MySQL 又这么多引擎。具体细分到每个表,不同的表引擎可以不一样。
新建一张表 t_test_myisam,引擎使用 MyISAM,查看原文件可以看到有 3 个文件
可以看到索引和数据是分开的,其中索引文件仅仅保存数据记录的地址,故属于非聚簇索引。
主键索引(Primary Index)
MyISAM 引擎使用 B+Tree 作为索引结构,叶节点的 data 存放的是数据记录的地址。如下图是 MyISAM 主键索引的原理图。
其中 Col1 为主键,可以看出看出 MyISAM 的索引文件仅保存数据记录的地址。
辅助索引(Secondary Index)
在 Col2 上建立一个辅助索引,如下图辅助索引原理图。
可以看到与主键索引没有任何区别,只不过主键索引的 key 是唯一的,而辅助索引的 key 可以重复。
MyISAM 中索引检索的算法为首先按照 B+Tree 搜索算法搜索索引,如果指定的 Key 存在,则取出其 data 域的值,然后以 data 域的值为地址,读取相应数据记录。
其中三个字段就是联合索引。
由于联合索引的出现,key 由多个列组成,列的排序决定了可命中索引的列数。也叫最左前缀匹配
。
索引只能用于查找 key 是否存在(相等),遇到范围查找(>,<,=,between,like 左匹配)等就不能进一步匹配。
新建一张表 t_test_innodb,引擎使用 InnoDB,查看原文件可以看到有 2 个文件
主键索引(Primary Index)
InnoDB 的索引和数据在一个文件当中。
按照 B+Tree 组织的一个索引结构。
叶节点保存了完整的数据记录和索引。这种索引就叫做聚簇索引。
索引的 Key 是数据的主键,因此 InnoDB 表数据文件本身就是主索引。
如下图:
可以看到叶节点包含了完整的数据记录。
因为 InnoDB 的数据文件本身要按照主键聚集,所以 InnoDB 要求必须有主键
。如果没有显式指定,则 MySQL 系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则 MySQL 自动为 InnoDB 表生成一个隐含字段 rowid 作为主键,这个字段长度为 6 个字节,类型为长整形。
辅助索引(Secondary Index)
辅助索引,将途中的第二行 name,作为索引如图:
InnoDB 表是基于聚簇索引建立的。聚簇索引这种实现方式使得按照主键的搜索十分高效,但是需要首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。
由于 InnoDB 索引的实现特性,推荐使用整形的自增主键。
有三点好处:
一是主索引的区别:InnoDB 的数据文件本身就是索引文件。而 MyISAM 的索引和数据是分开的。
二是辅助索引的区别:InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。而 MyISAM 的辅助索引和主索引没有多大区别。
InnoDB 存储引擎支持覆盖索引,即从辅助索引中就可以得到查询的记录,而不需要查询聚集索引中的记录,就是平时所说的不需要回表。
可以减少大量的 IO 操作。如果要查询辅助索引中不包含的字段,得先遍历辅助索引,再遍历聚集索引,而如果要查询的字段值在辅助索引上就有,就不用再查聚集索引了,这显然会减少 IO 操作。
联合索引是指对表上的多个列进行索引。如下图联合索引原理图
InnoDB 存储引擎支持覆盖索引,即从辅助索引中就可以得到查询的记录,不需要查询聚簇索引中的记录了。可以减少大量的 IO 操作。
如果要查询辅助索引中不含有的字段,得先遍历辅助索引,再遍历聚集索引,而如果要查询的字段值在辅助索引上就有,就不用再查聚集索引了,这显然会减少 IO 操作。
例如,联合索引(a,b,c,d), 查询条件 a=1 and b=3 and c>3 and d=4; 会依次命中 a,b,c,无法命中 d,这就是最左前缀匹配。
两个或以上的列上的索引。如下图联合索引的原理图:
上图中的联合索引有三个,从上到下,严格按照排序。
1、最左前缀匹配
索引可以简单如一个列 (a),也可以复杂如多个列 (a, b, c, d),即联合索引
。如果是联合索引,那么 key 也由多个列组成,同时,索引只能用于查找 key 是否存在(相等),遇到范围查询 (>、<、between、like 左匹配) 等就不能进一步匹配了,后续退化为线性查找。因此,列的排列顺序决定了可命中索引的列数。
如有索引 (a, b, c, d),查询条件 a = 1 and b = 2 and c > 3 and d = 4
,则会在每个节点依次命中 a、b、c,无法命中 d。也就是最左前缀匹配原则。
2、in 自动优化顺序
不需要考虑 =、in 等的顺序,mysql 会自动优化这些条件的顺序,以匹配尽可能多的索引列。
如有索引 (a, b, c, d),查询条件 c > 3 and b = 2 and a = 1 and d < 4 与 a = 1 and c > 3 and b = 2 and d < 4
等顺序都是可以的,MySQL 会自动优化为 a = 1 and b = 2 and c > 3 and d < 4
,依次命中 a、b、c。
索引列不能参与计算
有索引列参与计算的查询条件对索引不友好(甚至无法使用索引),如 from_unixtime(create_time) = '2021-08-27'。
原因很简单,如何在节点中查找到对应 key?如果线性扫描,则每次都需要重新计算,成本太高;如果二分查找,则需要针对 from_unixtime 方法确定大小关系。
因此,索引列不能参与计算。上述 from_unixtime(create_time) = '2021-08-27'
语句应该写成 create_time = unix_timestamp('2021-08-27')。
能扩展就不要新建索引
如果已有索引 (a),想建立索引 (a, b),尽量选择修改索引 (a) 为索引 (a, b)。
新建索引的成本很容易理解。而基于索引 (a) 修改为索引 (a, b) 的话,MySQL 可以直接在索引 a 的 B + 树上,经过分裂、合并等修改为索引 (a, b)。
不需要建立前缀有包含关系的索引
如果已有索引 (a, b),则不需要再建立索引 (a),但是如果有必要,则仍然需考虑建立索引 (b)。
选择区分度高的列作索引
很容易理解。如,用性别作索引,那么索引仅能将 1000w 行数据划分为两部分(如 500w 男,500w 女),索引几乎无效。
区分度
的公式是 count(distinct <col>) / count(*)
,表示字段不重复的比例,比例越大区分度越好。唯一键的区分度是 1,而一些状态、性别字段可能在大数据面前的区分度趋近于 0。