转载自：http://www.ituring.com.cn/article/986
作者：李松峰

发表于 2012-02-04 11:43

译者按：今天在翻译时无意中搜索到StackOverflow中的这篇文章（问答），觉得有必要翻译出来。不仅因为文章本身写得精彩，更重要的是它昭示了一个写文章（特别是技术文章）的重要法则——5W1H。 原文在此 How does database indexing work?（作者：Xenph Yan）

问：随着数据库的增大，既然索引的作用那么重要，有谁能抛开具体的数据库来解释一下索引的工作原理？

答：（我自己来回答这个问题，:o-)）

为什么需要索引

数据在磁盘上是以块的形式存储的。为确保对磁盘操作的原子性，访问数据的时候会一并访问所有数据块。磁盘上的这些数据块与链表类似，即它们都包含一个数据段和一个指针，指针指向下一个节点（数据块）的内存地址，而且它们都不需要连续存储（即逻辑上相邻的数据块在物理上可以相隔很远）。

鉴于很多记录只能做到按一个字段排序，所以要查询某个未经排序的字段，就需要使用线性查找，即要访问N/2个数据块，其中N指的是一个表所涵盖的所有数据块。如果该字段是非键字段（也就是说，不包含唯一值），那么就要搜索整个表空间，即要访问全部N个数据块。

然而，对于经过排序的字段，可以使用二分查找，因此只要访问log2 N个数据块。同样，对于已经排过序的非键字段，只要找到更大的值，也就不用再搜索表中的其他数据块了。这样一来，性能就会有实质性的提升。

什么是索引

索引是对记录按照多个字段进行排序的一种方式。对表中的某个字段建立索引会创建另一种数据结构，其中保存着字段的值，每个值又指向与它相关的记录。这种索引的数据结构是经过排序的，因而可以对其执行二分查找。

索引的缺点是占用额外的磁盘空间。因为索引保存在MyISAM数据库中，所以如果为同一个表中的很多字段都建立索引，那这个文件可能会很快膨胀到文件系统规定的上限。

索引的原理

首先，来看一个示例数据库表的模式：

1
2
3
4
5

字段名              数据类型         在磁盘上的大小
id (Primary key)   Unsigned INT     4 字节
firstName          Char(50)         50 字节
lastName           Char(50)         50 字节
emailAddress       Char(100)        100 字节

注意：这里用char而不用varchar是为了精确地描述数据占用磁盘的大小。这个示例数据库中包含500万行记录，而且没有建立索引。接下来我们就分析针对这个表的两个查询：一个查询使用id（经过排序的键字段），另一个查询使用firstName（未经排序的非键字段）。

示例分析一

对于这个拥有r = 5 000 000条记录的示例数据库，在磁盘上要为每条记录分配 R = 204字节的固定存储空间。这个表保存在MyISAM数据库中，而这个数据库默认的数据库块大小为 B = 1024字节。于是，我们可计算出这个表的分块因数为 bfr = (B/R) = 1024/204 = 5，即磁盘上每个数据块保存5条记录。那么，保存整个表所需的数据块数就是 N = (r/bfr) = 5000000/5 = 1 000 000。

使用线性查找搜索id字段——这个字段是键字段（每个字段的值唯一），需要访问 N/2 ＝ 500 000个数据块才能找到目标值。不过，因为这个字段是经过排序的，所以可以使用二分查找法，而这样平均只需要访问log2 1000000 = 19.93 = 20 个块。显然，这会给性能带来极大的提升。

再来看看firstName字段，这个字段是未经排序的，因此不可能使用二分查找，况且这个字段的值也不是唯一的，所以要从表的开头查找末尾，即要访问 N = 1 000 000个数据块。这种情况通过建立索引就能得到改善。

如果一条索引记录只包含索引字段和一个指向原始记录的指针，那么这条记录肯定要比它所指向的包含更多字段的记录更小。也就是说，索引本身占用的磁盘空间比原来的表更少，因此需要遍历的数据块数也比搜索原来的表更少。以下是firstName字段索引的模式：

1
2
3

字段名         数据类型        在磁盘上的大小
firstName     Char(50)        50 字节
（记录指针）    Special         4 字节

注意：在MySQL中，根据表的大小，指针的大小可能是2、3、4或5字节。

示例分析二

对于这个拥有r = 5 000 000条记录的示例数据库，每条索引记录要占用 R = 54字节磁盘空间，而且同样使用默认的数据块大小 B = 1024字节。那么索引的分块因数就是 bfr = (B/R) = 1024/54 = 18。最终这个表的索引需要占用 N = (r/bfr) = 5000000/18 = 277 778个数据块。

现在，再搜索firstName字段就可以使用索引来提高性能了。对索引使用二分查找，需要访问 log2 277778 = 18.09 = 19个数据块。再加上为找到实际记录的地址还要访问一个数据块，总共要访问 19 + 1 = 20个数据块，这与搜索未索引的表需要访问277 778个数据块相比，不啻于天壤之别。

什么时候用索引

创建索引要额外占用磁盘空间（比如，上面例子中要额外占用277 778个数据块），建立的索引太多可能导致磁盘空间不足。因此，在建立索引时，一定要慎重选择正确的字段。

由于索引只能提高搜索记录中某个匹配字段的速度，因此在执行插入和删除操作的情况下，仅为输出结果而为字段建立索引，就纯粹是浪费磁盘空间和处理时间了；这种情况下不用建立索引。另外，由于二分查找的原因，数据的基数性（cardinality）或唯一性也非常重要。对基数性为2的字段建立索引，会将数据一分为二，而对基数性为1000的字段，则同样会返回大约1000条记录。在这么低的基数性下，索引的效率将减低至线性查找的水平，而查询优化器会在基数性小于记录数的30%时放弃索引，实际上等于索引纯粹只会浪费空间。

查询优化器的原理

查询优化中最核心的问题就是精确估算不同查询计划的成本。优化器在估算查询计划的成本时，会使用一个数学模型，该模型又依赖于对每个查询计划中涉及的最大数据量的基数性（或者叫重数）的估算。而对基数性的估算又依赖于对查询中谓词选择因数（selection factor of predicates）的估算。过去，数据库系统在估算选择性时，要使用每个字段中值的分布情况的详尽统计信息，比如直方图。这种技术对于估算孤立谓词的选择符效果很好。然而，很多查询的谓词是相互关联的，例如 select count(*) from R where R.make='Honda' and R.model='Accord'。查询谓词经常会高度关联（比如，model='Accord'的前提条件是make='Honda'），而估计这种关联的选择性非常困难。查询优化器之所以会选择低劣的查询计划，一方面是因为对基数性估算不准，另一方面就是因为遗漏了很多关联性。而这也是为什么数据库管理员应该经常更新数据库统计信息（特别是在重要的数据加载和卸载之后）的原因。（译自维基百科：http://en.wikipedia.org/wiki/Query_optimizer。）

关于排序

表是一个集合的概念，所以除非你显式地指定 order by 来排序，否则数据库是不保证每次返回的结果顺序是一样的。只是保证在没有修改的情况下，返回的数量是相同的。

关于大小写

虽然SQL是不区分大小写的，但对于列名和表名和值可能在不同的数据库里有不同的对待（表名，列名值等可能是大小写敏感的）。

关于 select *

除非你确实需要表中的每一列，否则最好别使用*通配符。虽然使用通配符能让你自己省事，不用明确列出所需列，但检索不需要的列通常会降低检索和应用程序的性能。

关于 distinct

DISTINCT 关键字作用于所有列，不仅仅是跟在其后的那一列。

关于按列排序

通常 order by 子句使用的列将是为显示而选择的列，但实际上并不一定要这样，用非检索的列排序数据是完全合法的。

关于按列排序的顺序

order by 排序的顺序完全按规定进行。即按跟在 order by 后面的指定列顺序来排序，先排第一个列的数据，然后再排序第二个出现的列，第三个等等。

关于排序的位置

order by 列的位置号[, 列的位置号2，列的位置号3 …]。这个列的位置是指select 后跟着的列的位号，数字从1开始，即第一个列的序号为1，以此类推。

注意，这种order by 排序，必须是出现在select 后指定的列的，而不能够是非select出来的列。

升序，降序

ASC，DESC，这些关键字，只应用到直接按位于其前面的列名。默认情况下都是升序。

关于 between and

它的范围是包括开始值，也包括结束值。

关于选择 NULL 值的数据

不能用 where col = NULL，而要用 where col IS NULL

关于 and 和 or 的顺序

and 的优先级高于 or，所以 col1 = 10 or col2 = 11 and col3 = 13，会被RDBMS理解成：
col1 = 10 or （col2 = 11 and col3 = 13）。

自己可以显式加圆括号来按自己指定的逻辑进行。如

（col1 = 10 or col2 = 11） and col3 = 13，这样子括号里的就会优先进行。

所以，复杂点的SQL都建议显式地指定圆括号来指示逻辑顺序。

关于 IN 和 OR，IN的优点

1）IN操作符一般比一组OR操作符执行得更快。
2）IN的最大优点是可以包含其他的SELECT语句，更能动态建立WHERE子句
3）IN比OR的执行顺序更明确（与其他AND等组合时）

关于AVG()函数

AVG()函数只能用来确定特定数值列的平均值，而且列名必须作为函数参数给出。为了获得多个列的平均值，必须使用多个AVG()函数。
而且 AVG() 函数忽略列值为NULL的行。

关于COUNT()函数

使用COUNT(*)对表中行的数目进行计数，不管表列是否包含NULL都会统计。

使用COUNT(col)对表中特定值的行进行计数，但会忽略NULL值 。

关于MAX()，MIN()，SUM()

MAX()函数和MIN()函数和SUM()函数，都会会忽略列值为NULL的行。

关于 COUNT 和 DISTINCT 混合

如果指定列名，则DISTINCT只能用于COUNT(DISTINCT COL)。
但是DISTINCT不能用于COUNT(*)。而且DISTINCT后只能跟列名，不能用于计算或表达式。

关于GROUP BY

1）GROUP BY 子句可以包含任意数目的列，因而可以对分组进行嵌套，更细致地进行数据分组。

2）如果在GROUP BY子句中嵌套了分组，数据将在最后指定的分组上进行汇总。换句话说，在建立分组时，指定的所有列都一起计算（所以不能从个别的列取回数据）

3）GROUP BY子句中列出的每一列都必须是检索列或有效的表达式（但不能是聚集函数）。如果在SELECT中使用表达式，则必须在GROUP BY子句中指定相同的表达式。不能使用别名。

4）大多SQL实现不允许GROUP BY列带有长度可变的数据类型（如文本或备注型字段）

5）除聚集计算语句外，SELECT语句中的每一列都必须在GROUP BY子句中给出

6）如果分组中包含具有NULL值的行，则NULL将作为一个分组返回。如果列中有多行NULL值，它们将分为一组。

7）GROUP BY子句必须出现在WHERE子句之后，ORDER BY 子句之前。

关于 WHERE 和 HAVING 的区别

WHERE是分组之前过滤的，HAVING是分组之后过滤的。

关于SELECT语法顺序

1
2
3
4
5
6

SELECT
FROM
WHERE
GROUP BY
HAVING
ORDER BY

关于子查询

作为子查询的SELECT语句只能查询单个列。企图检索多个列将返回错误。

关于SELECT子查询

1

select (select xxx from xx) , col from xx2

这种子查询对检索出的每一行都会执行一次。

关于连接表

• 笛卡儿积：如果两个连接的表，没有连接条件的话，检索出的行数，将是第一个表中的行数 x 第二个表中的行数。

• 公共点：所有的连接，第一步都是做笛卡儿积。

交叉连接（cross join）

笛卡儿积的联结，也叫交叉连接(cross join)

等值连接（也叫内连接）两种方式

1
2
3

select a.col, b.col from a, b where a.pid = b.pid;
select a.col, b.col from a inner join b on a.pid = b.pid

但是根据ANSI SQL规范，首选的是第二种。

内连接（基于连接谓词将两张表(如 A 和 B)的列组合在一起，产生新的结果表。）

• 等值连接

相等连接 (equi-join，或 equijoin)，是比较连接(θ连接)的一种特例，它的连接谓词只用了相等比较。使用其他比较操作符(如 <)的不是相等连接

• 自然连接

自然连接比相等连接的进一步特例化。两表做自然连接时，两表中的所有名称相同的列都将被比较，这是隐式的。自然连接得到的结果表中，两表中名称相同的列只出现一次.

• 叉连接

交叉连接(cross join)，又称笛卡尔连接(cartesian join)或叉乘(Product)，它是所有类型的内连接的基础。把表视为行记录的集合，交叉连接即返回这两个集合的笛卡尔积。这其实等价于内连接的链接条件为”永真”，或连接条件不存在.

如果 A 和 B 是两个集合，它们的交叉连接就记为: A × B.

外连接

外连接并不要求连接的两表的每一条记录在对方表中都一条匹配的记录. 连接表保留所有记录 — 甚至这条记录没有匹配的记录也要保留. 外连接可依据连接表保留左表, 右表或全部表的行而进一步分为左外连接, 右外连接和全连接.

• 左外连接

若 A 和 B 两表进行左外连接, 那么结果表中将包含”左表”(即表 A)的所有记录, 即使那些记录在”右表” B 没有符合连接条件的匹配. 这意味着即使 ON 语句在 B 中的匹配项是0条, 连接操作还是会返回一条记录, 只不过这条记录的中来自于 B 的每一列的值都为 NULL. 这意味着左外连接会返回左表的所有记录和右表中匹配记录的组合(如果右表中无匹配记录, 来自于右表的所有列的值设为 NULL). 如果左表的一行在右表中存在多个匹配行, 那么左表的行会复制和右表匹配行一样的数量, 并进行组合生成连接结果.

• 右外连接

右外连接, 亦简称右连接, 它与左外连接完全类似, 只不过是作连接的表的顺序相反而已. 如果 A 表右连接 B 表, 那么”右表” B 中的每一行在连接表中至少会出现一次. 如果 B 表的记录在”左表” A 中未找到匹配行, 连接表中来源于 A 的列的值设为 NULL.

其实可以通过变换表位置来使用左外连接。

• 全连接

全连接是左右外连接的并集. 连接表包含被连接的表的所有记录, 如果缺少匹配的记录, 即以 NULL 填充.

自连接

自连接就是和自身连接.

优先使用自连接，而不是子查询

一般来说，DBMS处理连接远比处理子查询快得多。但应该都试一下，以确定哪一种的性能更好。

连接算法

• 嵌套循环
• 合并连接
• 哈希连接

集合查询：并（union）

在各个select语句之间加上关键字union就可以了。使用union时，默认情况下会自动去除重复的行。可以添加上 union all 来返回所有行，包括重复的。

限制

1）union中的每个查询必须包含相同的列、表达式或聚集函数（顺序并不要求）

2）列数据类型必须兼容：类型不必完全相同，但必须是DBMS可以隐含转换的类型

union中使用order by

在union时，只能使用一条order by 子句，它必须位于最后一条select语句之后。因为，对于结果集来说，不存在用一种方式排序一部分，而又用另一种方式排序另一部分的情况，因此，不允许使用多条order by 。

关于insert没给出列名的情况

如果没有显式给出列名，那么values后各列是对应它在表定义中出现的顺序的。

insert select 语句

1

insert into t (col1, col2) select col11, col2 from t2;

注意，是没有values的哦。

select into语句

SQLite：

1

select * into totable from fromtable;

PostgreSQL，MySQL，Oracle等的方式：

1

create table totable as select * from fromtable;

即，将fromtable表所有数据，复制到totable中。

关于视图

• 视图是不能索引的

• 视图是可以嵌套的（性能低）

• 视图包含的不是数据，而是根据需要检索数据的查询。视图提供了一种封装select语句的层次，可以用来简化数据处理，重新格式化或保护基础数据。

关于存储过程

• 简单（通过封装，将复杂逻辑放在一个单元中）

• 安全（简化表名，列名或业务逻辑等其他内容的变化时的管理）

• 高性能（存储过程是以编译后的形式存储的，所以DBMS处理命令的工作较少，从而提高性能）

关于游标

它是一个存储在DBMS服务器上的数据库查询，它不是一条SELECT语句，而是被该语句检索出来的结果集。

关于主键

• 任意两行的主键值都不相同

• 每行都具有一个主键值（即不允许NULL值）

• 包含主键值的列从不修改或更新（允许DBMS允许，也不要这样子做）

• 主键仁政不能重用。如果从表中删除某一行，其主键值不分配给新行。

唯一约束

• 表可以包含多个唯一约束，但只允许一个主键

• 可以包含NULL值

• 可以修改或更新

• 唯一约束，不能用来定义外键

关于索引

• 索引改善检索的性能，但降低了数据插入、修改和删除的性能。

• 索引数据可能要占用大量存储空间

• 并非所有数据都适合做索引。取值不多的数据，不如具有更多可能值的数据，能通过索引得到那么多的好处。

• 索引用于数据过滤和数据排序。

• 可以在索引中定义多列。这样子使用索引的要求时，必须按定义出现的索的顺序为前缀。