最近一篇发表于《程序员》2014年6月刊上的文章。有点遗憾发现，有些部分被编辑修改过了，读起来有点怪怪的。最典型的是习惯于对某些比较经典的定义引用wikipedia或者原始白皮书中原始的E文，在文中发现都被硬译过了，表达的意思自己都有点看不懂了！

最终修改后提交的版本归档下：

引言

关于数据库索引，随便Google一个Oracle index，Mysql index总能得到“某某索引之n条经典建议”之类大量结果。笔者认为，较之直接借鉴，在搞清实际需求的基础上，对备选方案的原理尽可能深入全面的了解会更有利于我们的决策。因为某种方案或者技术呈现出某种优势（包括可能没有被介绍到但一定存在的限制），不是厂商的白皮书这样规定，是由实现机制决定的或者说本身的结构决定的。

本文重点介绍数据结构中经典的树（B树）结构在数据库索引中的经典应用，也会涉及到几种数据库中对此支持的细微不同，以期比较完整的描述实现原理。最终会发现这几种被不同数据库厂商冠以不同名字的东西原理上其实差不多，理论上其实是一个东西。文中只是略微空洞的介绍其实现原理，不涉及应用上具体的使用建议。

关键字：B树 数据库索引 索引组织表（Index-Organized Tables） 聚集索引 非聚集索引 Oracle Mysql Mssql

一、关于数据库索引

数据库索引在维基中的定义：A database index is a data structure that improves the speed of data retrieval operations on a database table at the cost of additional writes and the use of more storage space to maintain the extra copy of data. Indexes are used to quickly locate data without having to search every row in a database table every time a database table is accessed.

如果Index被翻译成目录可能更能体现出其本质的作用。和其他很多计算机科学中的概念一样，Index也是现实事物中的一种常见结构。由目录最容易联想到的是图书馆的书籍管理，如果没有个目录，很难想象要从图书馆的那么多书架上找到一本书是多么困难的事情。

当然映射的最好的是小时候厚厚的新华字典前面的目录，对于字典中数据根据两种拼音和笔画(四角号码)两种属性进行索引。字典前面和后面多出来的那么几十页纸（额外的存储）的用处就是快速定位到字典中某个词条的完整记录。如果没有这个Index，要查找字典的某个字就只有full table scan一样的挨着翻页了。

二、关于B树索引

数据库中比较常用的索引结构有B树、位图等几种。其中B树是几乎所有数据库的默认索引结构，也是用的最多的索引结构。

索引的基本作用是用于查找。数据结构的查找算法中最基本的是顺序查找，即从列表上逐个匹配关键字，其时间复杂度是O(n)，当n比较大的时候这个效率是不能承受的。于是计算机科学尝试能不能在存储上做些文章发明效率更高的算法，然后就有了数据结构中我们熟悉的基于排序树的查找。B树（其实是B+树）是一种树的结构，通常用于数据库和操作系统的文件系统中。B+树的创造者Rudolf Bayer没有解释B代表什么。最常见的观点是B代表平衡(balanced)，因为所有的叶子节点在树中都在相同的级别上，B也可能代表Bayer，或者是波音（Boeing），因为他曾经工作于波音科学研究实验室。下图是一件简单的B树的例子。

 1Function: search (k)
 2  return tree_search (k, root);
 3Function: tree_search (k, node)
 4  if node is a leaf then
 5    return node;
 6  switch k do
 7  case k < k_0
 8    return tree_search(k, p_0);
 9  case k_i ≤ k < k_{i+1}
10    return tree_search(k, p_{i+1});
11  case k_d ≤ k
12    return tree_search(k, p_{d+1});

关于B树的一个性质，在数据库中采用的B树结构的索引，除了上面平衡树的基础特征外，结合数据库索引使用的需要，都有如下的结构要求。

• 内节点不存储data，只存储key和指向下级节点的指针；叶子节点不存储指针，存储真正的数据。即内节点的作用是导航，叶节点才真正存数据。不同的索引类型，叶节点data域存储的东西会有不同，导致查询也会不同。在后面会对此详细介绍。
• 在叶子节点上都会有个双向的指针指向相邻的叶子节点。提高在索引键上的区间访问的性能。

通常在B树上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点。因此可以对B树进行两种查找运算：一种是从最小关键字起顺序查找，另一种是从根节点开始，进行随机查找。

三、B树在数据库索引中的几种应用

结合数据库实现对B树结构的不同应用，主要是叶子节点存储的内容不同，把B树分为两种：一种是叶节点存完整的行数据，一种是叶节点只是存一个指向实际数据行的指针。根据表中数据存储格式不同，指针又分为物理指针和逻辑指针。这样B树的结构被分成三类：

• B树叶节点存完整数据的索引结构
• B树叶节点存物理指针的索引结构
• B树叶节点存逻辑指针的索引结构

听着都不太高大上。为了讨论方便，且这样分了。

(一)B树叶节点存物理指针的索引结构

这是最普通的一种索引结构。数据插入时存储位置是随机的，由数据库内部存储的空闲情况决定。这种表数据的存储结构称为堆表（heap table）。在堆表中记录是无序的，插入速度会比较快。但是查找一个数据会比较麻烦，需要扫描整个堆表才可以。如下图表T是示意的一个简单表，表上有三列。每行前十六进制数字仅示意该行的存储位置。

假设查找出C2=43的行，我们需要从第一行开始，逐行的检查每行上C2的取值。即使第三行找到了。但还是需要扫描接下来的行，因为不能保证在前方还有没有满足条件的行。对一个数据量比较大的表，这样的方式是不可以接受的。

于是乎就有了索引的概念，即另外开辟一个存储结构，按照某个列进行排序，并记录每行的在该列上取值的以及该行在表中的对应位置。这恐怕是索引本质的意思了吧。就像字典上某个拼音和页码的关系。

几乎所有的这类索引都采用B树结构。叶节点的key是索引列在每行上的值，而对应的data域保存了该行的一个引用，可理解为指向实际存储数据的指针。如图中在C2上建立索引，按照C2的属性构建B树，在每个叶节点上和索引键对应的都有一个指针记录该行数据的存储位置。尽管右下角的表上的数据是无序的，同样要找到C2=43的记录行，从索引树上只要经过三个节点即可以找到叶节点存储的指针，并通过指针找到对应的行。

因为几种数据库中最典型的索引，结构也就基本相同。Oracle 中直接根据存储结构把这种索引称为B树索引，索引叶节点存储(key: rowid)，其中rowid标识了该行的物理存储位置。

对于Mssql来说，这种索引称为非聚集索引。当没有创建聚集索引的时候，即表示表是以堆的形式(heap structure)存储。同样叶节点也是存储（key: RID），其中RID指定数据存储物理位置的行和页。

在Mysql 中索引结构因不同的存储引擎实现而不同。两种比较常用的存储引擎中,Myisam表上的数据总是按照堆的结果存储的，索引采用和上图类似的索引结构。详细点说Myisam上的主键索引、唯一索引、辅助索引都是这种结构。不同的是，主键索引要求选择的索引列是表的主键，唯一索引要求索引列取值的唯一性约束，而辅助索引没有这些要求。

(二)B树叶节点存数据的索引结构

B树构造的另外一种索引，与其说是一种索引方式，倒不如说是以一种表数据的存储方式（Oracle 中就称之为索引组织表）。这种结构的一个特点是B树的叶节点中和索引键对应存储的是实际的数据行。即（Key: Row）的结构。即在叶节点上完整的保存了数据行。如图，在C3列上构建索引，则整个表中的数据按照C3的顺序来存储。第一个叶节点上存储了C3=5和C3=25的完整的行，同时整个表按照C3取值的顺序存储。即整个表的数据按照C3列在聚集（哦，难怪在Mssql中这种结构被称为聚集索引）。

Oracle 中，不认为该种方式的存储是索引，而是更形象的称为索引组织表（Index-Organized Tables）；在Mssql中，这种结构正是其所谓的聚集索引（Clustered Index）；在Mysql 中， Innodb是支持这种结构的，称之为聚集（Clustered index）。即便三种数据库都支持该索引结构，其相互之间还是有些比较tricky的差别，这正是想对照着强调的。

• 在Oracle 的索引组织表根据主键排序后的顺序进行排列的，即索引的列必须是表的主键列，在建表的同时要指定主键约束，可以是单字段，也可以是复合主键约束。创建索引组织表时，必须要设定主键，否则报错。

• 在Mysql的Innodb的存储引擎中，Innodb的数据文件本身要按主键聚集，按主键顺序存储。所以Innodb要求表必须有主键，如果没有显式指定，Mysql系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则Mysql自动为Innodb表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

• 而在Mssql中，关于该索引列的要求就没有那么高，并未要求索引列必须是主键，也不要求该列上有唯一性约束。当在没有聚集索引的表上创建主键时，Mssql会自动在该主键列上创建一个聚集索引。当在没有唯一约束的列上创建聚集索引时，Mssql会自动的在重复的键值上添加一个4 byte的uniqueifier使得该值唯一，这个对用户是透明的。

  (三)B树叶节点存逻辑指针的索引结构

根据前面的描述，当表中数据按照传统堆结构组织的时候，构造索引（非聚集）的B树的叶节点上上存储（key: rowid）这样的结构，即关联到数据行的物理指针。但当数据本身是按照B树存储的时候，数据库认为有了逻辑标识一个行的标签，叶节点存储的对指针会稍有不同。不再存储一个物理指针，而是存储对应的聚集索引键这样一个逻辑指针，即叶节点上存储（key: clusterKey）这样的结构。如图，在C3上创建了聚集索引，C1上创建一个非聚集的索引。则在C1的索引树上叶节点处存储了C3取值作为聚集索引的键。如第三个叶子节点，C1对应的值为Inter，对应的聚集索引在该行的值为C3=151.即通过151这个cluster key来关联到实际数据行。数据行在另外一个按C3列构造的B树上存储。

因为几种数据库对于聚集索引的要求有细微差别，当存在聚集索引情况下的非聚集索引也相应的有所不同。

• 在Oracle 中，该索引称为辅助索引（Secondary Indexes on Index-Organized Tables）。因为Oracle 的索引组织表（Index-Organized Tables）的索引键必须是主键，则该辅助索引相应管理的是一个代表了主键的逻辑rowid。

• 在Mysql的Innodb中，和Oracle 几乎完全相同，这种索引也称为辅助索引（secondary indexes）。因为其聚集索引列也是要求必须是主键，相应辅助索引关联的也是对应的主键。

• 在Mssql中，这种索引称为非聚集索引(Nonclustered Index)。在B树的叶节点上存储索引列和聚集索引对应聚集索引键（clustered index key）。上面讨论聚集索引的时候说到过，Mssql的聚集索引的列不要求唯一性，也不要求是主键。但是为了非聚集索引能通过聚集索引键唯一定位到一行数据，在重复的聚集索引键上会添加一个唯一标示来使得其唯一，这个操作对用户是透明的。

  

如上图在C3上有重复的值，按照Mysql和Oracle 的要求，在该列上是不能创建聚集索引的，但是在Mssql中，在该列上可以建聚集索引。图示C3列有重复值的聚集索引的情况下在C1列上的构建非聚集索引，C1上创建的非聚集索引的每一行数据都能通过聚集索引key唯一关联到实际的数据行上。

msdn中关于no-clustered index的介绍：If the clustered index is not a unique index, SQL Server makes any duplicate keys unique by adding an internally generated value called a uniqueifier. This four-byte value is not visible to users. It is only added when required to make the clustered key unique for use in nonclustered indexes.

四、总结

为了更清晰的对照，整理出一个对照列表。发现大部分都是相同的，除了术语上，SQL语法上，或者某些约定限制的程度上稍有不同。因为原理是一样的。同样因为结构相同，造成使用也是完全相同。如：

• 根据聚集索引的检索方式；
• 有聚集索引时根据非聚集索引检索方式；
• 没有聚集索引时根据非聚集索引检索方式

再根据原理多分析一点，不是使用建议，只是这种结构提示给我们的信息。只说it is ,不说you should。

了解了聚集索引实现原理后，就能理解为什么不大建议在长字段上面建聚集索引，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大；也能理为什么说在聚集索引列上的查找，包括范围查找会比较高效，数据就是这样组织的；也能理解建了聚集索引后写入性能会怎样降低，因为数据组织有了约束，写入性能下降，插入/删除/更新聚集键值等，会导致记录的物理移动、页拆分等额外的磁盘操作；也不难理解非聚集的索引读数据时候，如果不能从索引上包含全部的查询列，需要关联表来查询，则会有两次查询，一次是从非聚集索引上定位到聚集索引键，然后再从聚集索引键查到数据。较之非聚集的索引，聚集索引也就只能有一个，也就相对珍贵些。一般选择会要比较慎重些。知道了这些原理后，对于到底要不要建聚集索引，根据业务特征在哪个列上创建，要不要创建非聚集索引，在哪个上创建，这些也就不难回答。很多时候这种选择其实是几种方案间的trade-off。即使理解了原理，在使用中几种方案实验结果的对照更能帮助我们做出正确的选择。有点像我们测试中的黑盒测试之于白盒测试的关系。

同样对于其他数据库方面的技术，通过Database System Concepts 中数据库一般理论的稍微抽象的观点了解、看待其在我们开发中的应用，可以使我们对这些技术的理解更系统、更深刻。当项目需要游走于多个数据库之间的时候，不至于都是拿着manual，拿着tuning的手册来完全的从零开始在在操作层面上被指导。

附：《程序员》原版

about-btrees-application-in-database-index-in-programmer