引入

MySQL数据库为研究对象，讨论与数据库索引相关的一些话题。特别需要说明的是，MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。

常见的查询算法以及数据结构

建立索引，其实就是为了构建一种数据结构，可以应用到上面的一种算法。提供查询的效率

索引的本质是：

帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。

如果没用索引的话，会按照上下顺序来查找，就会匹配整张表，这叫全表扫描，这样的效率是很低的。

而mysql中的索引是在引擎层中实现的

b+tree索引 最常见的 都支持

hash索引 精确匹配 memory支持

r-tree索引 空间位置 myisam支持

full-text索引 除了memory不支持其他都支持

b-tree多路平衡查找树

几阶b-tree就最多有几个节点，会有n+1个指针

查询算法

顺序查找：

对比每个元素的方法，不过这种算法在数据量很大时效率是极低的。

数据结构是队列

时间复杂度是O(n)

二分查找：

查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

数据结构是数组

时间复杂度：O(logn)

二叉排序树查找：

二叉排序树的特点是：

1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 它的左、右子树也分别为二叉排序树。

搜索的原理：

1. 若b是空树，则搜索失败，否则：
2. 若x等于b的根节点的数据域之值，则查找成功；否则：
3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：
4. 查找右子树。

数据结构是二叉排序树

时间复杂度：O(log2N)

哈希表：其原理是首先根据key值和哈希函数创建一个哈希表（散列表），燃耗根据键值，通过散列函数，定位数据元素位置。

数据结构：哈希表

时间复杂度：几乎是O(1)，取决于产生冲突的多少（hash碰撞）。

分块查找：

分块查找又称索引顺序查找，它是顺序查找的一种改进方法。其算法思想是将n个数据元素”按块有序”划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须”按块有序”；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，依次类推。
　　
算法流程：

1. 先选取各块中的最大关键字构成一个索引表；
2. 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。

这种搜索算法每一次比较都使搜索范围缩小一半。它们的查询速度就有了很大的提升，复杂度为。

如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

B-tree

B树，它就是一种平衡多路查找树。下图就是一个典型的B树：

满了中间元素向上分裂每一个key都会对应

由于B-Tree的特性，在B-Tree中按key检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。

关于B-Tree有一系列有趣的性质，例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2)，检索一个key，其查找节点个数的渐进复杂度为O(logdN)。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。

B+Tree

在b+树中所有的元素都会在叶子节点，叶子节点会形成一个单向链表，非叶子节点只会起到索引的作用

mysql的所有，会形成了一个带有顺序的指针b+tree

所有的数据都会在叶子节点，用来存储数据，存储在页中

特点：

• 每个节点的指针上限为2d而不是2d+1；
• 内节点不存储data，只存储key；
• 叶子节点不存储指针；

下面就是一个B+Tree

在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

为什么innodb引擎选择使用b+tree？

• 对于b+树对于二叉树的层级更少，搜索效率高

• 相对于b-ree无论是叶子节点还是非叶子节点，都会保存数据，会导致键值变少，指针变少，同样要保留大量数据，只能增加树的高度，导致性能降低

• 对于hash索引来说，可以范围索引和排序

涉及的计算机原理

两种类型的存储

在计算机系统中一般包含两种类型的存储，计算机主存（RAM）和外部存储器（如硬盘、CD、SSD等）。在设计索引算法和存储结构时，我们必须要考虑到这两种类型的存储特点。主存的读取速度快，相对于主存，外部磁盘的数据读取速率要比主从慢好几个数量级，具体它们之间的差别后面会详细介绍。 上面讲的所有查询算法都是假设数据存储在计算机主存中的，计算机主存一般比较小，实际数据库中数据都是存储到外部存储器的。

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，**索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。**下面详细介绍内存和磁盘存取原理，然后再结合这些原理分析B-/+Tree作为索引的效率。

主存存取原理

目前计算机使用的主存基本都是随机读写存储器（RAM），现代RAM的结构和存取原理比较复杂，这里本文抛却具体差别，抽象出一个十分简单的存取模型来说明RAM的工作原理。

从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址：通过一个行地址和一个列地址可以唯一定位到一个存储单元。上图展示了一个4 x 4的主存模型。

主存的存取过程如下：

当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。

这里可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响，例如，先取A0再取A1和先取A0再取D3的时间消耗是一样的。

磁盘存取原理

上文说过，索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作。与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。

磁盘读取数据靠的是机械运动，当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间，最后便是对读取数据的传输。 所以每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分。其中：

• 寻道时间是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下。
• 旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2 = 4.17ms。
• 传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。

那么访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17 = 9ms左右，听起来还挺不错的，但要知道一台500 -MIPS的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行40万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难。

局部性原理和磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

性能分析

B-Tree

先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h-1个节点（根节点常驻内存）。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。一个节点物理上也是存在一个页里面

B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

综上所述，如果我们**采用B-Tree存储结构，搜索时I/O次数一般不会超过3次，**所以用B-Tree作为索引结构效率是非常高的。

B+Tree

从上面介绍我们知道，B树的搜索复杂度为O(h)=O(logdN)，所以树的出度d越大，深度h就越小，I/O的次数就越少。B+Tree恰恰可以增加出度d的宽度，因为每个节点大小为一个页大小，所以出度的上限取决于节点内key和data的大小：

1

dmax=floor(pagesize/(keysize+datasize+pointsize))//floor表示向下取整

由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，从而拥有更好的性能。

B-树和B+树查找过程基本一致。如上图所示，如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。真实的情况是，**3层的b+树可以表示上百万的数据，**如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。

所以说很多数据的话，也只需要3次IO，这样的话效率就非常高了。

mysql中的索引

基础知识

索引的分类：

主键索引，对于主键的创建的索引，只能有一个，默认自动创建 primary

唯一索引，避免同一个表中的数据列的值重复，unique

常规索引 快速定位数据

全文索引 查找文本中的关键字，而不是索引中的值，关键词fulltext

还分为

聚集索引：数据存储和索引放在一个，必须有而且只能有一个

二级索引，将数据和索引分开，叶子节点关联的是对应的主键

聚集索引：

• 存在主键，主键索引就是聚集索引
• 不存在主键，将会引用第一个唯一索引作为聚集索引
• 没有主键，没有唯一索引，Innodb会自动生成一个rowid作为隐藏的聚集索引

回表查询：先走二级索引找到对应的主键值，再到聚集索引中拿到这一行的行数据

思考：

innodb的b+tree高度是多少？

16*1171^h,高度为h

语法：

创建索引：

1

CREATE [UNIQUE/FULLLTEXT] INDEX INDEX_NAME ON TABLE_NAME(INDEX_COL_NAME...);

一个索引是可以关联多个字段的

查看索引：

1

show index from table_name;

删除索引：

1

drop index index_name on table_name;

索引名字格式

1

idx_user_name;

实例：

1
2
3
4

CREATE INDEX idx_users_name ON uers(name);
CREATE  UNIQUE INDEX idx_users_email ON users(email);
CREATE INDEX idx_users_name_age ON users(name,age);
CREATE FULLTEXT INDXE id_users_bio ON users(bio);

1
2

SHOW INDEX FROM users;
DROP INDEX id_users_name ON users;

sql优化

查询当前数据的增删改查执行效率：

1

SHOW GLOBAL STATUS LIKE 'Com_______';

可以统计 Com_select、Com_insert、Com_update、Com_delete 等的执行次数，判断数据库的查询负载。

慢查询：

查询当前sql超时标准（默认long_query_time为10s，超过10s的记录才会查询）

1

SHOW VARIABLES LIKE 'long_query_time';

开启慢查询日志，编辑 /etc/my.cnf 或 my.ini（Windows）：

1
2
3

slow_query_log=1
long_query_time=2

查询慢查询日志文件

1

SHOW VARIABLES LIKE 'slow_query_log_file';

然后 cat 或 tail -f 这个文件，查看慢查询 SQL。

PROFILES：

查看sql执行的时间分析

1

SHOW PROFILES;

默认是关闭的状态，需要手动开启

1

SET profiling = 1;

执行查询完成后，再次查看

1

SHOW PROFILE CPU FOR QUERY 16;

这里 16 是 SHOW PROFILES 里查询的 Query_ID，可以查看具体 SQL 的 CPU 耗时 详情。

explain:

EXPLAIN + sql语句可以看到sql语句的执行情况

返回的详情为：

id:sql执行的顺序，数值越大，越先执行

select_type:

• simple 简单查询 不用表连接和子查询
• primary 主查询 即外层的查询
• union union后的查询 union中的第二个或者后面的查询语句
• subquery 子查询 select/where之后包含了子查询

type：查询类型，效率从高到低排序

• null
• system
• const
• eq_ref
• ref
• range
• index
• all 全表扫描

possible_keys：可能用到的索引

key:实际用到的索引

key_len：索引的长度

rows：预估扫描的行数

filtered:过滤后返回的行数占比，越大越好

索引的原则

最左前缀法则：

查询使用索引要从索引的最左列开始，不能跳过，跳过的话，后面的索引会失效。

必须包含最左边的一列，在哪无所谓，必须要存在

比如我们建立一个索引

1

CREATE INDEX idx_user_name_age ON users(name, age);

如果我们sql语句为

1
2

SELECT * FROM users WHERE name = 'Alice';
SELECT * FROM users WHERE name = 'Alice' AND age = 30;

这样的话索引不会失效，但是如果从age开始的话，索引就会失效了

1

SELECT * FROM users WHERE age = 30;

范围查询：

联合查询中，出现范围查询（<>）范围查询右侧的索引列失效

使用大于等于或者小于等于就可以避免后面的索引失效

比如我们建立一个索引

1

CREATE INDEX idx_user_name_age ON users(name, age);

进行精确查询，索引不会失效

1

SELECT * FROM users WHERE name = 'Alice' AND age = 30;

但是进行范围查询的时候，后面的索引就会失效了

1

SELECT * FROM users WHERE name = 'Alice' AND age > 25 AND city = 'New York';

索引列运算操作：

不饿能在索引列上进行运算操作，否则索引会失效

不能不加单引号，否则索引也会失效

1

SELECT * FROM users WHERE YEAR(created_at) = 2024;

这样索引会失效的

但是我们进行一些优化，进行范围查询（带着等于的），索引就不会失效了

1

SELECT * FROM users WHERE created_at >= '2024-01-01' AND created_at < '2025-01-01';

模糊查询：

尾部进行模糊查询，索引不会失效，头部进行模糊匹配索引会失效。

后面加%可以进行索引，前面加%索引就会失效，一般别写这种sql语句

尾部匹配是有效的

1

SELECT * FROM users WHERE name LIKE 'Alice%';

但是头部匹配索引就会失效

1

SELECT * FROM users WHERE name LIKE '%Alice';

如果我们想使用模糊匹配的话，可以使用FULLTEXT索引

1
2

CREATE FULLTEXT INDEX idx_users_bio ON users(bio);
SELECT * FROM users WHERE MATCH(bio) AGAINST('keyword');

这样来进行匹配查询

OR：

OR左右两侧都要有索引，否则索引会失效

1

SELECT * FROM users WHERE name = 'Alice' OR age = 30;

为了不让其失效，我们可以使用UNION ALL

1
2
3

SELECT * FROM users WHERE name = 'Alice'
UNION ALL
SELECT * FROM users WHERE age = 30;

数据分布影响索引：

索引适用于高选择性字段（不同值较多的列）

如果 查询大量数据，可能 全表扫描比索引更快，可以忽略索引

1

EXPLAIN SELECT * FROM users IGNORE INDEX(idx_user_name) WHERE status = 'active';

sql提示：

use index使用某个索引

1

EXPLAIN SELECT * FROM users USE INDEX(idx_user_name) WHERE name = 'Alice';

ignore index 忽略索引

1

EXPLAIN SELECT * FROM users IGNORE INDEX(idx_user_name) WHERE name = 'Alice';

force index 强制使用某个索引

1

EXPLAIN SELECT * FROM users FORCE INDEX(idx_user_name) WHERE name = 'Alice';

覆盖索引：

查询的字段都在索引列内，可以避免回表，提高查询效率

1
2

CREATE INDEX idx_user_name_age ON users(name, age);
SELECT name, age FROM users WHERE name = 'Alice'; -- 只查询索引列，避免回表

前缀过长：

适用于字符串索引过长的情况，只索引字符串的一部分

计算型索引（越接近1.0越好）

1

SELECT COUNT(DISTINCT email) / COUNT(*) FROM users;

前缀索引

1

CREATE INDEX idx_email_5 ON users(email(5)); -- 仅索引 email 前 5 个字符

联合索引：

更推荐联合索引，索引效率更加高效

1

CREATE INDEX idx_user_name_age ON users(name, age);

大原则：

• 数据量大，查询比较频繁的表要建立索引，对查询条件进行索引，尽量使用联合索引。
• 要使用区分度高的索引
• 字符串类型的索引，要建立前缀索引。要考虑前缀的区分度
• 要控制索引的效率
• 索引不能存储null值，建立表的时候要采用not null的约束