在数据库中，最常用的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 那么二叉树形成的索引结构如下图所示，
这种非平衡二叉树，在出现数据连续的情况，会使得二叉树变成链表。这种情况将严重影响查询性能，使得查询效率降低为O(n)，其中n是数据的数量，而不再是O(log n)。
这种链表化的二叉树通常称为退化的二叉树（Degenerate Binary Tree），它的高度和数据量成正比，而不再保持对数级别的高效性。退化的二叉树的查询时间复杂度退化为线性搜索，会使得索引的意义几乎丧失，造成数据库查询效率极低。
为了避免退化的二叉树情况，通常采用平衡二叉树作为索引数据结构，如AVL树和红黑树。
红黑树的五个性质：
- 每个节点要么是黑色，要么是红色，这是红黑树的最基本性质。
- 根节点必须是黑色，这确保了树的平衡性质。
- 叶子节点是指为空(NIL或NULL)的节点，它们也被认为是黑色的。这样做是为了简化红黑树的定义和实现。
- 红黑树的这个性质确保了没有两个相邻的红色节点，防止出现连续的红色节点，保持了树的平衡。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点,它确保了在最坏情况下，红黑树的高度不会超过其节点数的两倍，从而保持了树的平衡性能。
红黑树虽然解决了二叉树平衡性的问题，但在某些情况下，它的树高仍然会随着数据量的增加而增长，使得树的高度不断增大，从而导致查询性能下降。这是因为红黑树的自平衡特性，在插入和删除节点时，红黑树会通过旋转和颜色调整来保持树的平衡。这使得红黑树在大部分情况下可以保持相对平衡，但在某些特定情况下，可能无法避免树的高度增加。
通过二叉树和红黑树展示，我们可以看出，随着树的高度的增加从而导致了查询的时间复杂的增加；在数据库索引中，树的高度直接影响了寻找数据时所需的磁盘IO次数。树的高度越低，查询数据所需的磁盘IO次数就越少，从而提高了查询的性能。因此我们需要关注能够减少磁盘IO次数，优化数据访问效率的数据结构，B树和B+树都是多叉平衡搜索树，它们的设计目标正式如此。
- B树（B-tree）：B树是一种平衡的多叉搜索树，它的每个节点可以存储多个数据项（通常称为键或索引值）。B树的每个节点有多个子节点，子节点的个数称为B树的阶（order）。B树的特点是每个节点的数据项按照键的大小有序排列，同时保持整个树的平衡，即所有叶子节点到根节点的高度差不超过1。
- B+树（B+ tree）：B+树是在B树的基础上做了一些改进，它也是一种平衡的多叉搜索树。与B树不同的是，B+树的非叶子节点仅用于索引导航，不存储数据，而所有的数据项都存储在叶子节点中。叶子节点形成一个有序链表，可以更高效地进行范围查。
那为什么MySQL最终选择了B+树而没有选择B树呢？主要原因有四点：
- 数据存储方式
[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操作。
- 空间利用率
- 范围查询和排序操作
哈希索引的特性：
- 高效的等值查询：由于哈希索引直接通过哈希值查找存储位置，等值查询非常高效，时间复杂度为O(1)。在索引数据量较大的情况下，哈希索引通常比B+树索引更快。
- 不支持范围查询：由于哈希索引的特性是将索引键值映射到一个特定的存储位置，而不是形成有序结构，所以不支持范围查询，无法用于处理区间查询或排序操作。
- 冲突处理：由于哈希函数可能将不同的索引键值映射到相同的哈希值，这就产生了哈希冲突。数据库需要采用冲突解决策略，常见的解决方法是开链法（Chaining）或开放地址法（Open Addressing）。
4.索引的存储位置和文件类型
mysql 的数据存在data 目录下,根据不同的引擎来构建成不同的文件类型。 InnoDB存储引擎：在InnoDB中，表的数据和索引都存储在.ibd文件中。如果您在构建表时使用的引擎是InnoDB，则会生成.frm和.ibd文件。InnoDB使用B+树的数据结构来组织数据，而且使用聚簇索引。聚簇索引的叶子节点存储整行数据，因此数据的物理存储顺序与主键的逻辑顺序相同。这使得InnoDB的聚簇索引在某些情况下具有更好的性能，特别是对于范围查询和基于主键的查询。 在InnoDB存储引擎中，构建主键索引和非主键索引的叶子节点存储方式是不同的，这在查询时会产生不同的影响。 主键索引：对于构建在主键上的索引，其叶子节点存储的是数据行的实际数据和主键值。这意味着主键索引是覆盖索引（Covering Index），可以直接通过索引就能获取到查询所需的数据，无需回表查询。
非主键索引：对于构建在非主键列上的索引，其叶子节点存储的是索引列的键值和对应的主键值。在进行查询时，首先通过非主键索引找到对应的主键值，然后再根据主键值回表查询，获取到实际的数据。这就是所谓的"回表查询"，在查询非主键列的数据时，需要额外的I/O操作去获取实际的数据。
例子：假设我们有一个表 students，其中有主键 id 和非主键索引 name_index，索引结构如下：
主键索引： [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操作，因为数据可能不连续存储。
InnoDB的聚簇索引和MyISAM的非聚簇索引之间的差异在于数据的物理存储方式。聚簇索引将数据存储在叶子节点中，使得相关数据紧凑存储，而非聚簇索引则需要进行额外的指针查找来定位真正的数据行。因此，在选择存储引擎时，要考虑数据访问模式、性能需求和特定查询类型，以使得索引能够更好地满足您的应用需求。
联合索引分析
当一个索引由多个列组成，我们称之为联合索引（Composite Index）或复合索引。联合索引允许在多个列上进行查询，而不仅限于单独的列，这样可以更高效地支持涉及多个列的查询条件。
联合索引如何排序
联合索引的排序方式是按照联合索引的各个列顺序进行排序。在创建联合索引时，索引的第一个列按照其自身的排序规则进行排序，如果存在相同的值，则根据索引的第二个列排序，依此类推。这样可以形成一个多级排序的结构，以便快速地定位到满足查询条件的数据行。
假设有一个表 products，其中包含联合索引 (category, brand, price)，并且索引的各个列的排序方式分别如下：
联合索引 (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 不是联合索引的第一个列，而是第二个列，所以这个查询无法充分利用联合索引的排序顺序。在这种情况下，数据库引擎可能无法使用联合索引，而需要进行全表扫描来查找满足条件的数据行。 因此，创建联合索引时，要根据实际查询需求和数据的访问模式，选择合适的列顺序，以提高查询性能。如果查询条件中的列与联合索引的前缀列匹配，索引可以有效利用，但如果与后面的列匹配，索引的效率可能会降低。 联合索引的特性：
- 覆盖索引：当查询涉及到的列都包含在联合索引中，并且索引的列顺序与查询条件的顺序一致时，联合索引就可以成为覆盖索引，从而避免回表查询，提高查询性能。
- 索引选择性：联合索引的选择性是指索引中不同列的唯一组合数量。选择性越高，索引在过滤数据时可以更快地定位到目标行。通常情况下，选择性越高，索引的效率越高。
- 最左前缀匹配：对于联合索引，最左前缀匹配是指索引从最左边的列开始匹配查询条件。在某些情况下，只有最左边的列被用于查询时，索引才会被利用。如果查询涉及到索引的连续部分，但不是从最左边开始，那么联合索引的效率会降低。
标签：存储,查询,索引,深入,Mysql,键值,主键,节点
From： https://www.cnblogs.com/PxgComeOn/p/17579000.html