在数据库中,最常用的SQL操作之一就是SELECT语句,它负责数据的检索。而在SELECT语句背后,与索引的交互密不可分。为了优化数据库性能和加快查询速度,开发者们往往优先考虑调整索引。 让我们深入了解索引的背后故事。这篇文章将从什么是索引,索引的分类,索引的底层数据数据结构,跟大家一起来学习索引。
1.什么是索引
在数据库中,索引是一种数据结构,它可以加快数据库表中数据的检索速度。当在数据库表中创建索引时,数据库管理系统会根据指定的字段或列创建一个索引结构,以便在查询数据时可以更快地找到匹配的记录,而不必逐条扫描整个表。 Mysql官网是这样描述的:索引用于快速查找具有特定列值的行。如果没有索引,MySQL 必须从第一行开始,然后读取整个表以查找相关行。表越大,成本就越高。如果表有相关列的索引,MySQL 可以快速确定要在数据文件中间查找的位置,而无需查看所有数据。这比顺序读取每一行要快得多。2.索引的分类
- 按照数据结构分类
- B+树索引:B+树索引是一种常见的索引类型,它使用B+树数据结构进行组织,适用于各种查询条件,包括精确匹配和范围查询。
- Hash索引:Hash索引使用哈希算法将索引值映射到哈希表中的槽位,适用于精确匹配查找,不支持范围查询。
- Full-text索引:Full-text索引用于对文本字段进行全文搜索,支持模糊匹配和关键词搜索。
- 按照索引在数据库中的角色分类
- 聚簇索引(也称为聚集索引):聚簇索引是按照索引列的顺序直接组织表中的数据。在InnoDB存储引擎中,主键索引就是聚簇索引,用于标识表中每一行,并决定了表中数据的物理存储顺序。
- 二级索引(也称为辅助索引):二级索引是基于聚簇索引之外的其他列构建的索引,包含索引列的值和对应的主键值,用于加快特定查询的速度。
- 按照索引的特性分类
- 主键索引(Primary Key Index):用于标识表中每一行的索引,每张表只能有一个主键索引。
- 唯一索引(Unique Index):确保索引列的值是唯一的,不允许重复值。
- 普通索引(Normal Index):最基本的索引类型,允许出现重复值和NULL值。
- 前缀索引(Prefix Index):对索引列的前缀进行索引,节省存储空间但可能牺牲查询精确性和性能。
- 其他索引分类
- 稀疏索引:稀疏索引是一种针对包含大量重复值的列的索引。它只保存索引列中不重复的值和对应的指针,以减少索引的存储空间。
3.索引的数据结构分析
从数据结构的角度来看来可以当做索引的数据结构有很多种例如,二叉树,红黑树,B-树,B+树,Hash,为什么MySQL会选择B+树来当做默认的索引呢。这里推荐大家使用Data Structure Visualization来对数据结构进行分析。 Data Structure Visualization https://www.cs.usfca.edu/~galles/visualization/about.html 首先我们来看二叉树,二叉树是一种有序的树状数据结构,每个节点最多有两个子节点:左子节点和右子节点。并且左子树的节点值小于等于父节点的值,右子树的节点值大于等于父节点的值。那么当二叉树作为索引结构时,假如我们的id是1,2,3,4,5,6,连续的id 那么二叉树形成的索引结构如下图所示,![0](/i/l/?n=23&i=blog/924666/202307/924666-20230725095004006-1627646719.png)
- 每个节点要么是黑色,要么是红色,这是红黑树的最基本性质。
- 根节点必须是黑色,这确保了树的平衡性质。
- 叶子节点是指为空(NIL或NULL)的节点,它们也被认为是黑色的。这样做是为了简化红黑树的定义和实现。
- 红黑树的这个性质确保了没有两个相邻的红色节点,防止出现连续的红色节点,保持了树的平衡。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点,它确保了在最坏情况下,红黑树的高度不会超过其节点数的两倍,从而保持了树的平衡性能。
![0](/i/l/?n=23&i=blog/924666/202307/924666-20230725095003230-1373300625.png)
- B树(B-tree):B树是一种平衡的多叉搜索树,它的每个节点可以存储多个数据项(通常称为键或索引值)。B树的每个节点有多个子节点,子节点的个数称为B树的阶(order)。B树的特点是每个节点的数据项按照键的大小有序排列,同时保持整个树的平衡,即所有叶子节点到根节点的高度差不超过1。
![0](/i/l/?n=23&i=blog/924666/202307/924666-20230725095004165-2081614305.png)
![0](/i/l/?n=23&i=blog/924666/202307/924666-20230725095004786-622758259.png)
- B+树(B+ tree):B+树是在B树的基础上做了一些改进,它也是一种平衡的多叉搜索树。与B树不同的是,B+树的非叶子节点仅用于索引导航,不存储数据,而所有的数据项都存储在叶子节点中。叶子节点形成一个有序链表,可以更高效地进行范围查。
![0](/i/l/?n=23&i=blog/924666/202307/924666-20230725095004032-1217371312.png)
![0](/i/l/?n=23&i=blog/924666/202307/924666-20230725095004807-163505011.png)
- 数据存储方式
[20, 40, 60] / | \ [5, 10] [25, 30] [45, 50, 55, 58] 假设我们有一个B树的节点最大容量为3的情况。 在这个B树中,每个节点存储的键值数量不定,但都在一个范围内。每个非叶子节点既存储索引键值,又存储实际数据。 例如,节点[20, 40, 60]包含键值20、40和60,并且包含对应的子节点的指针。这样的设计使得B树在查找特定键值时,不仅可以找到索引位置,还可以直接获取数据。 [40] / | \ [5, 10, 20]-> [30, 35] ->[45, 50, 55, 58] 假设我们有一个B+树的节点最大容量为3的情况。 在这个B+树中,每个节点存储的索引键值数量更多,相比于B树,它具有更高的空间利用率。每个非叶子节点仅存储索引键值,而所有的数据项都存储在叶子节点中。 例如,节点[40]仅包含键值40,并且包含指向叶子节点的指针。这使得B+树的非叶子节点更加紧凑,只用于索引导航,不占用额外的空间来存储数据。
- 范围查询性能
[20, 40, 60] / | \ [5, 10] [25, 30] [45, 50, 55, 58] 假设我们要进行键值在10到30之间的范围查询。范围查询需要在不同的层级之间跳转,增加了IO操作。 [40] / | \ [5, 10, 20]-> [30, 35] ->[45, 50, 55, 58] 范围查询只需在叶子节点之间遍历有序链表,不需要在不同的层级之间跳转,减少了IO操作。
- 空间利用率
- 范围查询和排序操作
![0](/i/l/?n=23&i=blog/924666/202307/924666-20230725095004202-1717456589.png)
- 高效的等值查询:由于哈希索引直接通过哈希值查找存储位置,等值查询非常高效,时间复杂度为O(1)。在索引数据量较大的情况下,哈希索引通常比B+树索引更快。
- 不支持范围查询:由于哈希索引的特性是将索引键值映射到一个特定的存储位置,而不是形成有序结构,所以不支持范围查询,无法用于处理区间查询或排序操作。
- 冲突处理:由于哈希函数可能将不同的索引键值映射到相同的哈希值,这就产生了哈希冲突。数据库需要采用冲突解决策略,常见的解决方法是开链法(Chaining)或开放地址法(Open Addressing)。
4.索引的存储位置和文件类型
mysql 的数据存在data 目录下,根据不同的引擎来构建成不同的文件类型。 InnoDB存储引擎:在InnoDB中,表的数据和索引都存储在.ibd文件中。如果您在构建表时使用的引擎是InnoDB,则会生成.frm和.ibd文件。InnoDB使用B+树的数据结构来组织数据,而且使用聚簇索引。聚簇索引的叶子节点存储整行数据,因此数据的物理存储顺序与主键的逻辑顺序相同。这使得InnoDB的聚簇索引在某些情况下具有更好的性能,特别是对于范围查询和基于主键的查询。 在InnoDB存储引擎中,构建主键索引和非主键索引的叶子节点存储方式是不同的,这在查询时会产生不同的影响。 主键索引:对于构建在主键上的索引,其叶子节点存储的是数据行的实际数据和主键值。这意味着主键索引是覆盖索引(Covering Index),可以直接通过索引就能获取到查询所需的数据,无需回表查询。![0](/i/l/?n=23&i=blog/924666/202307/924666-20230725095004032-1217371312.png)
![0](/i/l/?n=23&i=blog/924666/202307/924666-20230725095004203-142565784.png)
主键索引: [1: Alice] [2: Bob] [3: Charlie] [4: David] ... 非主键索引: [Alice: 1] [Bob: 2] [Charlie: 3] [David: 4] ...如果我们执行以下查询: SELECT * FROM students WHERE id = 2; 由于主键索引是覆盖索引,查询引擎可以直接从主键索引中获取到id=2对应的数据行。而如果我们执行以下查询: SELECT * FROM students WHERE name = 'Bob'; 由于name是非主键列,查询引擎首先会通过name_index找到name='Bob'对应的主键值(在本例中是id=2),然后再根据主键值回表查询,获取到实际的数据行。 因此,在InnoDB中,对于非主键列的查询可能会产生回表查询的额外开销,而对于主键列的查询则可以直接利用主键索引的覆盖索引特性,避免回表查询,提高查询性能。 MyISAM存储引擎:在MyISAM中,表的数据和索引分别存储在.myd和.myi文件中。如果您在构建表时使用的引擎是MyISAM,则会生成.frm、.myd和.myi文件。MyISAM也使用B+树的数据结构来组织数据,但是它使用非聚簇索引。非聚簇索引的叶子节点存储的是主键值的映射指针和地址,而不是真正的数据行。在MyISAM中,数据的物理存储顺序与主键的逻辑顺序不一定相同。这意味着在MyISAM中,对于范围查询或基于主键的查询,可能需要进行更多的磁盘I/O操作,因为数据可能不连续存储。
![0](/i/l/?n=23&i=blog/924666/202307/924666-20230725095004805-1507682918.png)
联合索引 (category, brand, price) 排序: (Computers, Dell, 1000) (Computers, HP, 800) (Computers, Lenovo, 900) (Electronics, Samsung, 600) (Electronics, Sony, 700) (Furniture, Ikea, 300) (Furniture, Ashley, 400) (Furniture, Wayfair, 500) ...
在这个联合索引中,首先按照category列的排序顺序进行排序,如果category相同,则按照brand列的排序顺序进行排序。如果category和brand都相同,则按照price列的排序顺序进行排序。这样的多级排序结构可以快速定位满足查询条件的数据行。 例如,如果执行以下查询: SELECT * FROM products WHERE category = 'Computers' AND brand = 'Dell'; 由于查询条件涉及到联合索引的前两个列 category 和 brand,数据库引擎可以直接使用联合索引快速定位到满足条件的数据行,而无需扫描整张表。 然而,如果执行以下查询: SELECT * FROM products WHERE brand = 'Dell' AND price < 1000; 由于查询条件中的列 brand 不是联合索引的第一个列,而是第二个列,所以这个查询无法充分利用联合索引的排序顺序。在这种情况下,数据库引擎可能无法使用联合索引,而需要进行全表扫描来查找满足条件的数据行。 因此,创建联合索引时,要根据实际查询需求和数据的访问模式,选择合适的列顺序,以提高查询性能。如果查询条件中的列与联合索引的前缀列匹配,索引可以有效利用,但如果与后面的列匹配,索引的效率可能会降低。 联合索引的特性:
- 覆盖索引:当查询涉及到的列都包含在联合索引中,并且索引的列顺序与查询条件的顺序一致时,联合索引就可以成为覆盖索引,从而避免回表查询,提高查询性能。
- 索引选择性:联合索引的选择性是指索引中不同列的唯一组合数量。选择性越高,索引在过滤数据时可以更快地定位到目标行。通常情况下,选择性越高,索引的效率越高。
- 最左前缀匹配:对于联合索引,最左前缀匹配是指索引从最左边的列开始匹配查询条件。在某些情况下,只有最左边的列被用于查询时,索引才会被利用。如果查询涉及到索引的连续部分,但不是从最左边开始,那么联合索引的效率会降低。
![0](/i/l/?n=23&i=blog/924666/202307/924666-20230725095004953-1011246337.png)