目录
一、前言
在前面的文章中，我们已经介绍了B-树、B+树和B*树，并对他们各自的优势和局限性也做了讲解。其中B-树和B+树是平常应用最多的，它们最常见的应用就是索引，本文就是来着重探讨B-树在索引方面的应用。
二、索引
1、了解索引
在之前我们已经了解过数据库方面的知识，当数据量很大时，为了能够方便管理数据，提高数据查询的效率，一般都会选择将数据保存到数据库，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护着满足特定查找算法的数据结构.
数据库的核心任务是快速查询数据。最基础的查询方法是顺序查找（从头到尾扫一遍），但它在数据量大时效率很低（时间复杂度 O(n)）。好在有更高效的算法，比如二分查找和二叉树查找。
不过，这些高效算法有个前提：数据必须按照特定的方式组织好。比如，二分查找要求数据排好序，二叉树查找需要数据存储在二叉查找树里。但现实中的数据很难同时满足所有这些组织结构要求（比如，你很难让同一份数据同时按两个不同字段都排好序）。
为了解决这个问题，数据库系统会在原始数据之外，额外创建一些专门辅助查找的数据结构——这就是索引。索引就像是指路牌或目录，它通过某种方式引用（指向）实际的数据记录，并且本身的结构设计得很适合高效查找算法（比如树结构）。这样，数据库就能先在索引上利用高级算法快速定位到目标数据的位置，然后再去获取实际的数据内容。
MySQL官方对索引的定义为：索引(index)是帮助MySQL高效获取数据的数据结构，简单来说： 索引就是数据结构
总的来说，索引就是一个排序的列表，在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址（类似于c语言的链表通过指针指向数据记录的内存地址)。使用索引后可以不用扫描全表来定位某行的数据，而是先通过索引表找到该行数据对应的物理地址然后访问相应的数据，因此能加快数据库的查询速度。索引是表中一列或者若干列值排序的方法。(如MySQL中的主键索引)
简单来说索引就好比是一本书的目录，可以根据目录中的页码快速找到所需的内容。建立索引的目的是加快对表中记录的查找或排序。
2、索引的优缺点
优点：
- 大幅提速查询： 尤其是当数据量庞大或查询涉及多表关联时，索引能帮助数据库利用高效的定位技术（如树查找），将查询速度提升数个数量级。
- 降低系统负载：
- 减少磁盘读写(I/O)： 索引就像一个精确的导航图，让数据库能快速找到目标数据的位置，避免了逐行扫描整个表的巨大磁盘开销。
- 省去排序成本： 如果索引本身已经按查询所需的顺序组织好了数据（如排好序），数据库在执行
ORDER BY排序或GROUP BY分组操作时，可以直接利用索引的顺序，避免额外的排序步骤。
- 确保数据唯一性： 创建唯一性索引能强制保证表中每行数据的某个字段（或字段组合）值是唯一的，防止重复录入。
- 加速表间连接(JOIN)： 在进行表连接操作时，索引可以帮助数据库快速定位关联表中的匹配行，显著提升连接效率。
- 提升数据搜索性能： 总而言之，索引的核心价值在于极大优化了数据的搜索(
WHERE)、排序(ORDER BY)、分组(GROUP BY)、恢复(SELECT)以及表连接(JOIN)等操作的性能。
缺点：
- 索引需要占用额外的磁盘空间。对于 MyISAM 引擎而言，索引文件和数据文件是分离的，索引文件用于保存数据记录的地址。而 InnoDB 引擎的表数据文件本身就是索引文件。
- 更新一个包含索引的表需要比更新一个没有索引的表花费更多的时间，这是由于索引本身也需要更新。因此，理想的做法是仅仅在常常被搜索的列（以及表）上面创建索引。
3、如何创建索引
- 没有索引的情况下，要查询某行数据，需要先扫描全表来定位某行数据
- 有索引后会通过查找条件的字段值找到其索引对应的行数据的物理地址，然后根据物理地址访问相应的数据。
如上图所示，该图的左边是一张数据表，它共有两列，包含七条数据，其中最左侧记录的是数据的物理地址(逻辑上相邻的记录在磁盘上也并不是一定物理相邻的),假设我们此时想要查找 23 ，如果没有索引则需要扫描全表进行全表查询，为了方便查询，我们为了右边所示的二叉搜索树，这样我们就可以通过三次查询即可查到想要的数据。
三、MySQL数据库索引
如上图所示，是MySQL数据库的架构图，MySQL的架构遵循**“客户端-服务端”模式(C/S)，核心分为5层**：客户端连接层、连接池与管理层、SQL处理层、插件式存储引擎层、底层存储层。
顶层：客户端连接层（Connectors）:提供多语言/工具的连接接口，实现客户端与MySQL Server的通信。MySQL 通过网络通信来实现对数据库中数据的增删查改操作。
第二层：连接池与管理层（Connection Pool）：管理客户端连接，优化资源利用率（避免频繁创建/销毁线程）。
第三层：SQL处理层（SQL Processing Layer）：处理SQL语句的全生命周期（从接收请求到生成执行计划），是MySQL的“大脑”。该层有Caches & Buffers（缓存与缓冲区），是用来缓存高频查询的结果或中间数据，减少磁盘I/O。
第四层：插件式存储引擎层（Pluggable Storage Engines）：负责数据的存储与检索，是MySQL的核心特色（区别于Oracle等传统数据库）。该层包含着不同的存储引擎，允许用户根据需求选择不同的存储引擎（每个引擎有独立的实现），甚至自定义存储引擎。如InnoDB（默认引擎）、MyISAM
底层：存储层（File System & Files/Logs）：与操作系统交互，存储数据和日志文件。如文件系统。
值得注意的是，我们上面所提到的索引都是基于表的，而不是基于数据库的！！！！
在本文的第二节的如何创建索引时，我们举了一个二叉搜索树来提高数据库查找效率的例子，但是在实际中，数据库系统几乎没有使用二叉搜索树或其进化品种红黑树实现的，目前大部分数据库系统及文件系统都采用B-树或其变种B+树作为索引结构。这是为什么呢？
- 哈希表：哈希虽然能够提供
O(1)的单数据行的查询性能，但是对于 范围查询 和 排序 却无法很好支持，需全表扫描。- 红黑树：是一种自平衡二叉查找树，在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。一般对于数据库了来说，数据体量很大，构建索引本身也很大，往往不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗远远高于内存，所以评价一个数据结构作为索引的优劣最重要的指标就是查找过程中磁盘I/O次数。换句话说，索引的结构组织要尽量减少查找过程中磁盘 I/O 的次数。在这里，磁盘I/O的次数取决于树的高度，所以，在数据量较大时，红黑树会因为树的高度较大而造成磁盘 I/O 较多，从而影响查询效率。
四、磁盘 I/O 与局部性原理
1、磁盘 I/O
在正式介绍MySQL索引的数据结构之前，我们还需要先来了解一些预备知识。
先来了解一些有关于磁盘I/O的操作，在之前的文章中专门讲解过，可以回顾磁盘管理系统一文。简单来说就是由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘 I/O。这就需要提到 局部性原理了。
2、局部性原理
局部性原理（Locality Principle）是计算机系统中最核心的性能优化理论之一，描述了CPU访问内存时的偏好性，分为时间局部性（Temporal Locality）和空间局部性（Spatial Locality），两者共同决定了内存访问的模式。
- 时间局部性：如果一个数据/指令被访问过，那么在不久的将来，它很可能会被再次访问。
- 应用：缓存，将最近访问的数据保存在高速缓存中，下次访问时直接从缓存取（无需访问内存），提升速度。
- 空间局部性：如果一个数据/指令被访问过，那么它相邻地址的数据/指令很可能会被访问。
- 内存预读（Memory Prefetching）：当CPU访问一个内存块时，内存控制器会自动将相邻的内存块（如后面的64字节）加载到缓存中。例如，访问
arr时，内存会预读arr-arr（假设缓存行大小为64字节，每个int占4字节，16个int正好64字节），这样访问arr时，数据已经在缓存中了。 - 磁盘预读（Disk Prefetching）：硬盘读取数据时，会将相邻的扇区（如后面的几个扇区）一起读入内存。例如，读取文件的第1个扇区后，硬盘会预读第2、3、4个扇区，因为文件通常是连续存储的，接下来很可能会访问这些扇区。
- 内存预读（Memory Prefetching）：当CPU访问一个内存块时，内存控制器会自动将相邻的内存块（如后面的64字节）加载到缓存中。例如，访问
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。
预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
五、B-树与B+树
我们先看B-树作为索引数据结构为什么这么高效？通过前面对B-树的学习，我们已经知道B-树的结构可以使得磁盘I/O次数降到极低（通常不超过3次）。
我们知道索引的效率本质是减少磁盘I/O次数（因为磁盘I/O是计算机系统中最慢的操作之一，比内存访问慢约1000倍）。B-树的设计完美贴合磁盘的预读原理（局部性原理的体现），数据库设计者通过将每个节点的大小设为等于一个磁盘页（比如4KB），从而实现每个节点只需一次I/O即可完全载入内存。这样，
- 读取一个节点时，磁盘会把该节点所在的整页读入内存（一次I/O）；
- 不需要多次I/O读取一个节点（如果节点比页大，需要多次I/O；如果节点比页小，会浪费预读的空间）。
实现技巧：新建节点时，直接申请一个页的空间，确保节点物理上存储在一个页里，且计算机存储分配按页对齐（比如内存地址是4KB的整数倍），这样读取节点时不会跨页，只需一次I/O。
检索：
- 根节点常驻内存：因为根节点是检索的起点，频繁访问，所以数据库系统会将根节点常驻内存（不需要I/O）。
- 检索路径：检索一个key时，从根节点（内存）开始，比较key与节点中的键，找到对应的子节点，然后读取该子节点（一次I/O），重复这个过程直到叶子节点（所有叶子节点在同一层）。
- I/O次数：假设B-Tree的高度为
h（根节点是第1层，叶子节点是第h层），则检索一次需要**h-1次I/O**（根节点不需要I/O，下一层到叶子节点需要h-1次I/O）。
且出度d（B-Tree每个节点的子节点数量，比如d=100，即每个节点最多有100个子节点，99个键）越大，树的高度h越小，检索的I/O次数越少，效率越高。
而对于二叉搜索树、红黑树这类数据结构来说，如果由它们建立数据库索引，则树高度会很大，效率不够高，此外由于逻辑上很近的节点（父子）物理上可能很远，也无法利用局部性，效率明显比B-树差很多。
对于B+树来说，它是对B-树的优化，其是内外索引的主流选择，特别是外索引，原因和内节点出度d有关。从上面分析可以看到，越大的数据量，d越大索引的性能越好，而B-树出度受限于节点内存的不仅是key还有数据，B+树则舍弃掉了非叶子节点的数据，只在非叶子节点存储索引，数据全部存储在叶子节点，因此可以拥有更大的出度，拥有更好的性能。
六、MySQL的索引原理
在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，在前文已经提到了MySQL有着多种存储引擎，本文主要讨论 MyISAM 和 InnoDB 两个存储引擎的索引实现方式。
1、 MyISAM引擎
MyISAM引擎是MySQL5.5.8版本之前默认的存储引擎，不支持事物，支持全文检索，使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：
如上图所示，假设该表一共有三列，我们以 第一列(Col) 为主键，则上图是一个 MyISAM 表的主索引（Primary key）示意。可以看出 MyISAM 的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：
如上图所示，同样也是一颗B+树，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+树搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
可以看到，MyISAM 索引文件 和 数据文件 是分离的，索引文件仅保存数据记录的地址，因此MyISAM的索引方式也叫做非聚集的，之所以这么称呼是为了与InnoDB的聚集索引区分。
2、InnoDB引擎
InnoDB存储引擎支持事务，其设计目标主要面向在线事务处理的应用，从MySQL数据库5.5.8版 本开始，InnoDB存储引擎是默认的存储引擎。InnoDB支持B+树索引、全文索引、哈希索引。但 InnoDB使用B+树作为索引结构时，具体实现方式却与MyISAM截然不同。
第一个区别是InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的， 索引文件仅保存数据记录的地址。而InnoDB索引，表数据文件本身就是按B+树。组织的一个索 引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此 InnoDB表数据文件本身就是主索引。
InnoDB主索引（同时也是数据文件）的示意图如下：
，可以看到叶节点包含了完整的数据记录， 这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。
第二个区别是对于InnoDB来说，所有辅助索引（非主键索引）中的叶子节点并不直接指向数据行的实际存储位置（即磁盘地址），而是存储了对应记录的主键值。当通过辅助索引查询数据时，首先根据辅助索引找到对应的主键值，然后使用这个主键值去主键索引（聚集索引）中查找实际的数据行。这种方式有时被称为“两次查找”。如下图所示是定义在Col3上的一个辅助索引
这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
了解了MySQL的底层索引数据结构我们就能明白，为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。 再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，相比之下，使用自增整数作为主键可以有效地避免这个问题。新的记录总是被添加到B+树的末尾，极少需要进行页分裂，因此大大提高了插入效率。此外，整数类型的主键相比字符串类型更加紧凑，进一步减少了存储和索引开销。这也正是为什么在许多应用场景中推荐使用自增ID作为主键的原因之一。
在使用InnoDB存储引擎时，如果没有特别的需要，请永远使用一个与业务无关的自增字段作为主键。
InnoDB使用聚集索引，数据记录本身被存于主索引（一颗B+Tree）的叶子节点上。这就要求同一个叶子节点内（大小为一个内存页或磁盘页）的各条数据记录按主键顺序存放，因此每当有一条新的记录插入时，MySQL会根据其主键将其插入适当的节点和位置，如果页面达到装载因子（InnoDB默认为15/16），则开辟一个新的页（节点）。
如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页，这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。
七、索引的优化
MySQL的优化主要分为结构优化（Scheme optimization）和查询优化（Query optimization）。本章讨论的高性能索引策略主要属于结构优化范畴。实际上一旦理解了索引背后的机制，那么选择高性能的策略就变成了纯粹的推理，并且可以理解这些策略背后的逻辑。
1、联合索引
在上文中，我们都是假设索引只引用了单个的列，实际上，MySQL中的索引可以以一定顺序引用多个列，这种索引叫做联合索引，一般的，一个联合索引是一个有序元组<a1, a2, …, an>，其中各个元素均为数据表的一列。
联合索引（Composite Index），也称为组合索引，是指在数据库表的多个列上创建的索引。通过这种方式，可以在一个查询中同时利用这些列来加速数据检索。联合索引对于优化那些经常基于多个条件进行查询的SQL语句特别有用。
在一个或多个列上创建联合索引时，实际上是在这些列的值组合基础上构建了一个B+树结构。这意味着索引会按照从左到右的顺序对这些列进行排序，并且只有当查询条件中包含了索引最左侧的列时，该索引才能被有效使用。
2、索引选择性
在本文中我们一直在讨论索引，那我们就要思考一个问题，是不是只要是查询语句需要，就建上索引？答案是否定的。因为索引虽然加快了查询速度，但索引也是有代价的：索引文件本身要消耗存储空间，同时索引会加重插入、删除和修改记录时的负担，另外，MySQL在运行时也要消耗资源维护索引，因此索引并不是越多越好。一般两种情况下不建议建索引。
- 第一种情况是表记录比较少，例如一两千条甚至只有几百条记录的表，没必要建索引，让查询做全表扫描就好了。
- 另一种不建议建索引的情况是索引的选择性较低。索引选择性是指索引列中不同值的数量与总记录数的比例。简单来说，它衡量了一个索引能够区分数据行的能力。选择性越高（接近1），索引在查询中的效率就越高，因为高选择性的索引可以更精确地定位到特定的数据行，减少需要扫描的数据量。
- 高选择性索引：例如，在一个包含用户信息的表中，“电子邮件”字段通常具有很高的选择性，因为每个用户的电子邮件地址都是独一无二的。
- 低选择性索引：如“性别”字段，只有两种或三种可能的值（男、女等），这样的索引选择性就很低，对于查询优化的帮助不大。
3、前缀索引
有一种与索引选择性有关的索引优化策略叫做前缀索引，就是用列的前缀代替整个列作为索引key，当前缀长度合适时，可以做到既使得前缀索引的选择性接近全列索引，同时因为索引key变短而减少了索引文件的大小和维护开销。
通俗来讲，为了节省存储空间和提高索引效率，我们并不需要对整个字段建立索引，而是只需要对字段的前几个字符进行索引。例如，在一个包含URL的表中，如果你发现大多数URL的前20个字符已经足以区分它们，那么你可以为这前20个字符创建一个前缀索引，而不是对整个URL建立索引。
需要注意的是前缀索引兼顾索引大小和查询速度，但是其缺点是不能用于ORDER BY和GROUP BY操作，也不能用于Covering index（即当索引本身包含查询所需全部数据时，不再访问数据文件本身）。
感谢阅读！