数据结构与算法

数据结构与算法（1）：链表

线性表是⼀种线性结构，它是具有相同类型的n个数据元素组成的优先序列。介绍线性表的⼏个基本组成部分：数组、单向链表、双向链表。

⼀、数组

数组有上界和下界，数组的元素在上下界内是连续的。存储10，20，30，40，50的数组的示意图如下：

数组的特点是：数据是连续的；随机访问速度块。数组中稍微复杂⼀点的是多维数组和动态数组。对于Java⽽⾔，Collection集合中提供了ArrayList和Vector。

⼆、单向链表

2.1 定义

单向链表（单链表）是链表的⼀种，它由节点组成，每个节点都包含下⼀个节点的指针。单链表的示意图如下：

表头为空，表头的后继节点是“节点10”（数据为10的节点），“节点10”的后继节点是“节点20”（数据为20的结点）......

2.2 单链表删除节点

删除“节点30”删除之前：“节点20”的后继节点为“节点30”，⽽“节点30”的后继节点为“节点40”删除之后：“节点20”的后继节点为“节点40”

2.3 单链表添加节点

在“节点10 ”与“节点20”之间添加“节点15”添加之前：“节点10”的后继节点为“节点20”添加之后：“节点10”的后继节点为“节点15”，⽽“节点15”的后继节点为“节点20”。

单链表的特点是：节点的链接⽅向是单向的；相对于数组来说，单链表的随机访问速度较慢，但是单链表删除、添加数据的效率很⾼。

三、双向链表

3.1 定义

双向链表（双链表）是链表的⼀种。和单链表⼀样，双链表也是由节点组成，它的每⼀个数据节点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表的任意⼀个节点开始，都可以很⽅便地访问它的前驱结点和后继节点。

⼀般我们都构造双向循环链表。双链表的示意图如下：

表头为空，表头的后继节点为“节点10”（数据为10的结点）；“节点10”的后继节点是“节点20”（数据为10的节点），“节点20”的前继节点是“节点10”；“节点20”的后继节点是“节点30”，“节点30”的前继节点是“节点20”;......；末尾节点的后继节点是表头。

3.2 双链表删除节点

删除“节点30”删除之前：“节点20”的后继节点为“节点30”，“节点30”的前继节点为“节点20”。“节点30”的后继节点为“节点40”，“节点40”的前继节点为“节点30”删除之后：“节点20”的后继节点为“节点40”，“节点40”的前继节点为“节点20”

3.3 双链表添加节点

在"节点10"与"节点20"之间添加"节点15"添加之前："节点10"的后继节点为"节点20"，"节点20" 的前继节点为"节点10"。添加之后："节点10"的后继节点为"节点15"，"节点15" 的前继节点为"节点10"。"节点15"的后继节点为"节点20"，"节点20" 的前继节点为"节点15"。

数据结构与算法（2）：栈与队列

⼀、栈

1.1 栈的定义

栈（stack）是限定仅在表尾进⾏插⼊和删除操作的线性表。允许插⼊和删除的⼀端称为栈顶（top），另⼀端称为栈底，不含任何数据元素的栈称为空栈。它有以下⼏个特点：栈中的数据是按照“后进先出（LIFO，Last In First Out）”⽅式进出栈的。向栈中添加、删除数据时，只能从栈顶进⾏操作栈通常包括的三种操作：push、peek、poppush：向栈中添加元素；peek：返回栈顶元素；pop：返回并删除栈顶元素的操作。

1.2 进栈与出栈

下图为栈的示例图，栈中的数据依次为：30 => 20 => 10

下图为出栈的示意图：

出栈前：栈顶元素是30。此时，栈中的元素依次是30 => 20 => 10

出栈后：30出栈之后，栈顶元素变成20。此时，栈中的元素依次是 20 => 10

下图为⼊栈的示意图：

⼊栈前：栈顶元素是20。此时，栈中的元素依次是20 => 10

⼊栈后：40⼊栈之后，栈顶元素变成40。此时，栈中的元素依次是 40 => 20 => 10

⼆、队列

2.1 队列的定义

队列（queue）是只允许在⼀段进⾏插⼊操作，⽽在另⼀端进⾏删除操作的线性表。允许插⼊的⼀段称为队尾，允许删除的⼀端称为队头。它有以下⼏个特点：队列中数据是按照“先进先出（FIFO，First-In-First-Out）”⽅式进出队列的。队列只允许在“队⾸”进⾏删除操作，⽽在“队尾”进⾏插⼊操作。

2.2 出队列和⼊队列

下图为队列的示意图：

队列中有10，20，30共3个数据

下图为出队列的示意图：

出队列前：队⾸是10，队尾是30。

出队列后：出队列(队⾸)之后。队⾸是20，队尾是30。

下图为⼊队列的示意图：

⼊队列前：队⾸是20，队尾是30。

⼊队列后：40⼊队列(队尾)之后。队⾸是20，队尾是40。

数据结构与算法（3）：⼆叉树

数据结构中有很多树的结构，这⾥整理了⼆叉树、⼆叉查找树、AVL树、红⿊树、B树、B+树、trie树的基本概念与操作。

⼀、⼆叉树的概念

1.1 树的基本概念

树是⼀种数据结构，它是由n（n>=1）个有限节点组成⼀个具有层次关系的集合。

它具有以下特点：

每个节点有零个或多个⼦节点；

没有⽗节点的节点称为根节点；

每⼀个⾮根节点有且只有⼀个⽗节点；

除了根节点外，每个⼦节点可以分为多个不相交的⼦树。

若⼀个结点有⼦树，那么该结点称为⼦树根的"双亲"，⼦树的根是该结点的"孩⼦"。有相同双亲的结点互为"兄弟"。⼀个结点的所有⼦树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。

结点的度：结点拥有的⼦树的数⽬

叶⼦：度为零的结点。

分⽀结点：度不为零的结点

树的度：树中结点的最⼤的度。

层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1。

树的⾼度：树中结点的最⼤层次。

⽆序树：如果树中结点的各⼦树之间的次序是不重要的，可以交换位置。

有序树：如果树中结点的各⼦树之间的次序是重要的, 不可以交换位置。

森林：0个或多个不相交的树组成。对森林加上⼀个根，森林即成为树；删去根，树即成为森林。

1.2 ⼆叉树的定义

⼆叉树是每个节点最多有两个⼦树（不存在度⼤于2的结点）的树结构。⼆叉树的⼦树有左右之分，次序不能颠倒。它有5种基本形态：⼆叉树可以是空集；根可以有空的左⼦树或右⼦树；或者左右⼦树皆为空。

1.3 ⼆叉树的性质

1.3.1 性质⼀

⼆叉树的第i层⾄多有2^(i−1)个结点；

1.3.2 性质⼆

k−1深度为k的⼆叉树⾄多有2^(k−1)个结点；

1.3.3 性质三

包含n个结点的⼆叉树的⾼度⾄少为log2(n + 1)；

1.3.4 性质四

对任何⼀颗⼆叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1

1.4 满⼆叉树和完全⼆叉树

1.4.1 满⼆叉树

满⼆叉树的定义：除最后⼀层⽆任何⼦节点外，每⼀层上的所有结点都有两个⼦结点。也可以这样理解，除叶⼦结点外的所有结点均有两个⼦结点。节点数达到最⼤值，所有叶⼦结点必须在同⼀层上。

满⼆叉树的性质：

1. ⼀棵树的深度为h，最⼤层数为k，深度与最⼤层数相同，k=h；

2. 叶⼦数为2h

3. 第k层的结点数是：2k−1；

4. 总结点数是2k − 1，且总节点数⼀定是奇数。

1.4.2 完全⼆叉树

定义：⼀颗⼆叉树中，只有最⼩⾯两层结点的度可以⼩于2，并且最下⼀层的叶结点集中在靠左的若⼲位置上。这样的⼆叉树称为完全⼆叉树。

特点：叶⼦结点只能出现在最下层和次下层，且最⼩层的叶⼦结点集中在树的左部。显然，⼀颗满⼆叉树必定是⼀颗完全⼆叉树，⽽完全⼆叉树未必是满⼆叉树。

注意：完全⼆叉树是效率很⾼的数据结构，堆是⼀种完全⼆叉树或者近似完全⼆叉树，所以效率极⾼，像⼗分常⽤的排序算法、Dijkstra算法、Prim算法等都要⽤堆才能优化，⼆叉排序树的效率也要借助平衡树来提⾼，⽽平衡性基于完全⼆叉树

⼆、⼆叉树的遍历

【提问】

1. 请分别写出并解释⼆叉树的先序、中序、后续遍历的递归与⾮递归版本

2. 给定⼆叉树的先序跟后序遍历，能不能将⼆叉树重建：不能;

因为先序为⽗节点-左节点-右节点，后序为左节点-右节点-⽗节点，两者的拓扑序列是⼀样的，所以⽆法建⽴；

如果换成⼀棵⼆叉搜索树的后续能不能建⽴：可以，因为只要将遍历结果排序就可以得到中序结果。

这块内容讨论⼆叉树的常⻅遍历⽅式的代码（java）实现，包括前序（preorder）、中序（inorder）、后序（postorder）、层序（levelorder），进⼀步考虑递归和⾮递归的实现⽅式。递归的实现⽅法相对简单，但由于递归的执⾏⽅式每次都会产⽣⼀个新的⽅法调⽤栈，如果递归层级较深，会造成较⼤的内存开销，相⽐之下，⾮递归的⽅式则可以避免这个问题。递归遍历容易实现，⾮递归则没那么简单，⾮递归调⽤本质上是通过维护⼀个栈，模拟递归调⽤的⽅法调⽤栈的⾏为。

2.1 前序遍历

2.1.1 递归实现

递归实现很简单，在每次访问到某个节点时，先输出节点值，然后再依次递归的对左⼉⼦、右⼉⼦调⽤遍历的⽅法。代码如下

2.1.2 ⾮递归实现

利⽤栈实现循环先序遍历⼆叉树，维护⼀个栈，将根节点⼊栈，只要栈不为空，出栈并访问，接着依次将访问节点的右节点、左节点⼊栈。这种⽅式是对先序遍历的⼀种特殊实现，简洁明了，但是不具备很好地扩展性，在中序和后序⽅式中不适⽤。

还有⼀种⽅式就是利⽤栈模拟递归过程实现循环先序遍历⼆叉树。这种⽅式具备扩展性，它模拟了递归的过程，将左⼦树不断的压⼊栈，直到null，然后处理栈顶节点的右⼦树。

2.2 中序遍历

2.2.1 递归实现

2.2.2 ⾮递归实现

利⽤栈模拟递归过程实现循环中序遍历⼆叉树。跟前序遍历的⾮递归实现⽅法⼆很类似。唯⼀的不同是访问当前节点的时机：前序遍历在⼊栈前访问，⽽中序遍历在出栈后访问。

2.3 后序遍历

2.3.1 递归实现

2.3.2 ⾮递归实现

2.4 层序遍历

总结⼀下：树的遍历主要有两种，⼀种是深度优先遍历，像前序、中序、后序；另⼀种是⼴度优先遍历，像层次遍历。在树结构中两者的区别还不是⾮常明显，但从树扩展到有向图，到⽆向图的时候，深度优先搜索和⼴度优先搜索的效率和作⽤还是有很⼤不同的。深度优先⼀般⽤递归，⼴度优先⼀般⽤队列。⼀般情况下能⽤递归实现的算法⼤部分也能⽤堆栈来实现。

数据结构与算法（4）：⼆叉查找树

⼀、定义

⼆叉排序树（Binary Sort Tree）⼜称为⼆叉查找树（Binary Search Tree）、⼆叉搜索树。它是特殊的⼆叉树：对于⼆叉树，假设x为⼆叉树中的任意⼀个结点，x节点包含关键字key，节点x的key值记为key[x] 。如果y是x的左⼦树中的⼀个结点，则key[y] <= key[x] ；如果y是x的右⼦树的⼀个结点，则key[y] >= key[x] 。那么，这棵树就是⼆叉查找树。

⼆叉查找树是先对待查找的数据进⾏⽣成树，确保树的左分⽀的值⼩于右分⽀的值，然后再就⾏和每个节点的⽗节点⽐较⼤⼩，查找最合适的范围。这个算法的效率查找效率很⾼，但是如果使⽤这种查找⽅法要⾸先创建树。

它或者是⼀颗空树，或者是具有下列性质的⼆叉树：

1. 若任意节点的左⼦树不为空，则左⼦树上的所有节点的值均⼩于它的根结点的值；

2. 若任意节点的右⼦树不为空，则左⼦树上所有节点的值均⼩于它的根结点的值；3. 任意节点的左、右⼦树也分别为⼆叉查找树。

4. 没有键值相等的节点。

⼆叉查找树的性质：对⼆叉查找树进⾏中序遍历，即可得到有序的数列.

构造⼀颗⼆叉排序树的⽬的，其实并不是为了排序，⽽是为了提⾼查找和插⼊删除关键字的速度。不管怎么说，在⼀个有序数据集上的查找，速度总是要快于⽆序的数据集的，⽽⼆叉排序树这样的⾮线性结构，也有利于插⼊和排序的实现

⼆叉查找树的⾼度决定了⼆叉查找树的查找效率。

⼆、查找、插⼊与删除

2.1 查找

在⼆叉查找树中查找x的过程如下：

1. 若⼆叉树是空树，则查找失败。

2. 若x等于根结点的数据，则查找成功，否则。

3. 若x⼩于根结点的数据，则递归查找其左⼦树，否则。

4. 递归查找其右⼦树。

复杂度分析，它和⼆分查找⼀样，插⼊和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插⼊和删除元素的时候，树没有保持平衡（⽐如，我们查找上图（b）中的“93”，我们需要进⾏n次查找操作）。我们追求的是在最坏的情况下仍然有较好的时间复杂度，这就是平衡查找树设计的初衷。

根据上述的步骤，写出其查找操作的代码：

2.2 插⼊

插⼊：从根结点开始逐个与关键字进⾏对⽐，⼩了去左边，⼤了去右边，碰到⼦树为空的情况就将新的节点连接。⼆叉查找树的插⼊过程如下

1) 若当前的⼆叉查找树为空，则插⼊的元素为根节点;

2) 若插⼊的元素值⼩于根节点值，则将元素插⼊到左⼦树中;

3) 若插⼊的元素值不⼩于根节点值，则将元素插⼊到右⼦树中。

2.3 删除

如果要删除的节点是叶⼦，直接删；如果只有左⼦树或只有右⼦树，则删除节点后，将⼦树连接到⽗节点即可；如果同时有左右⼦树，则可以将⼆叉排序树进⾏中序遍历，取将要被删除的节点的前驱或者后继节点替代这个被删除的节点的位置。

⼆叉查找树的删除，分三种情况进⾏处理：

1) p为叶⼦节点，直接删除该节点，再修改其⽗节点的指针（注意分是根节点和不是根节点），如图a;

2)p为单⽀节点（即只有左⼦树或右⼦树）。让p的⼦树与p的⽗亲节点相连，删除p即可（注意分是根节点和不是根节点），如图b;

3)p的左⼦树和右⼦树均不空。找到p的后继y，因为y⼀定没有左⼦树，所以可以删除y，并让y的⽗亲节点成为y的右⼦树的⽗亲节点，并⽤y的值代替p的值；或者⽅法⼆是找到p的前驱x，x⼀定没有右⼦树，所以可以删除x，并让x的⽗亲节点成为y的左⼦树的⽗亲节点。如图c。

2.4 总结

⼆叉排序树总结：

⼆叉排序树以链式进⾏存储，保持了链式结构在插⼊和删除操作上的优点。

在极端情况下，查询次数为1，但最⼤操作次数不会超过树的深度。也就是说，⼆叉排序树的查找性能取决于⼆叉排序树的形状，也就引申除了后⾯的平衡⼆叉树。

给定⼀个元素集合，可以构造不同的⼆叉排序树，当它同时是⼀个完全⼆叉树的时候，查找的时间复杂度为O(log(n))，近似于⼆分查找。

当出现最极端的斜树时，时间复杂度为O(n)，等同于顺序查找，效果最差

下图为⼆叉树查找和顺序查找以及⼆分查找性能的对⽐图：

基于⼆叉查找树进⾏优化，进⽽可以得到其他的树表查找算法，⽐如平衡树、红⿊树等⾼效算法。

数据结构与算法（5）：AVL树

我们知道，对于⼀般的⼆叉搜索树（Binary Search Tree），其期望⾼度（即为⼀棵平衡树时）为log2n，其各操作的时间复杂度O(log2n) 同时也由此⽽决定。但是，在某些极端的情况下（如在插⼊的序列是有序的时），⼆叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建⽴⼆叉搜索树来尽量的避免这种情况，但是在进⾏了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数⽬减少，以⾄于树向左偏沉。这同时也会造成树的平衡性受到破坏，提⾼它的操作的时间复杂度。于是就有了我们下边介绍的平衡⼆叉树。

⼀、平衡⼆叉树

平衡⼆叉树定义：平衡⼆叉树（Balanced Binary Tree）⼜被称为AVL树（有别于AVL算法），且具有以下性质：它是⼀棵空树或它的左右两个⼦树的⾼度差的绝对值不超过1，并且左右两个⼦树都是⼀棵平衡⼆叉树。平衡⼆叉树的常⽤算法有红⿊树、AVL树等。在平衡⼆叉搜索树中，我们可以看到，其⾼度⼀般都良好地维持在O(log2n)，⼤⼤降低了操作的时间复杂度。

其严格定义为：⼀颗空树是平衡⼆叉树；若T是⼀棵⾮空⼆叉树，其左、右⼦树为TL和TR，令hl和hr分别为左、右⼦树的深度。当且仅当

• TL、TR都是平衡⼆叉树；

• 并且满⾜公式 |hl − hr| ≤ 1时，则T是平衡⼆叉树

  
  

相应地，定义 hl − hr为⼆叉平衡树的平衡因⼦（balance factor）。因此，平衡⼆叉树上所有结点的平衡因⼦可能是-1，0，1。换⾔之，若⼀颗⼆叉树上任⼀结点的平衡因⼦的绝对值都不⼤于1，则该树就是平衡⼆叉树。

最⼩⼆叉平衡树的节点的公式如下：F(n) = F(n − 1) + F(n − 2) + 1

这个类似于⼀个递归的数列，可以参考Fibonacci数列，1是根节点， F(n − 1)是左⼦树的节点数量，F(n − 2)是右⼦树的节点数量。

⼆、平衡查找树（AVL树）

2.1 AVL树的定义

平衡⼆叉树（AVL树，发明者的姓名缩写）：⼀种⾼度平衡的排序⼆叉树，其每⼀个节点的左⼦树和右⼦树的⾼度差最多等于1。平衡⼆叉树⾸先必须是⼀棵⼆叉排序树！

平衡因⼦（Balance Factor）：将⼆叉树上节点的左⼦树深度减去右⼦树深度的值。对于平衡⼆叉树所有包括分⽀节点和叶节点的平衡因⼦只可能是-1,0和1，只要有⼀个节点的因⼦不在这三个值之内，该⼆叉树就是不平衡的。

最⼩不平衡⼦树：距离插⼊结点最近的，且平衡因⼦的绝对值⼤于1的节点为根的⼦树。

n个结点的AVL树最⼤深度约1.44log2n。查找、插⼊和删除在平均和最坏情况下都是O(logn)。增加和删除可能需要通过⼀次或多次树旋转来重新平衡这个树。这个⽅案很好的解决了⼆叉查找树退化成链表的问题，把插⼊，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插⼊和删除牺牲掉O(logN)左右的时间，不过相对⼆叉查找树来说，时间上稳定了很多。

可以采⽤动态平衡技术保持⼀个平衡⼆叉树。构造平衡⼆叉树的时候，也可以采⽤相同的⽅法，默认初始时，是⼀个空树，插⼊节点时，通过动态平衡技术对⼆叉树进⾏调整。

Adeleon-Velskii和Landis提出了⼀个动态地保持⼆叉排序树平衡的⽅法，其基本思想是：在构造⼆叉排序树的过程中，每当插⼊⼀个结点时，⾸先检查是否因插⼊⽽破坏了树的平衡性，若是因插⼊结点⽽破坏了树的平衡性，则找出其中最⼩不平衡树，在保持排序树特性的前提下，调整最⼩不平衡⼦树各结点之间的连接关系，以达到新的平衡。通常这样得到的平衡⼆叉排序树简称为AVL树。

2.2 AVL树的⾃平衡操作——旋转

AVL树最关键的也是最难的⼀步操作就是旋转。旋转主要是为了实现AVL树在实施了插⼊和删除操作以后，树重新回到平衡的⽅法。下⾯我们重点研究⼀下AVL树的旋转。

2.2.1 不平衡的四种情况

对于⼀个平衡的节点，由于任意节点最多有两个⼉⼦，因此⾼度不平衡时，此节点的两颗⼦树的⾼度差2。容易看出，这种不平衡出现在下⾯四种情况：

1) 6节点的左⼦树3节点⾼度⽐右⼦树7节点⼤2，左⼦树3节点的左⼦树1节点⾼度⼤于右⼦树4节点，这种情况成为左左。

2) 6节点的左⼦树2节点⾼度⽐右⼦树7节点⼤2，左⼦树2节点的左⼦树1节点⾼度⼩于右⼦树4节点，这种情况成为左右。

3) 2节点的左⼦树1节点⾼度⽐右⼦树5节点⼩2，右⼦树5节点的左⼦树3节点⾼度⼤于右⼦树6节点，这种情况成为右左。

4) 2节点的左⼦树1节点⾼度⽐右⼦树4节点⼩2，右⼦树4节点的左⼦树3节点⾼度⼩于右⼦树6节点，这种情况成为右右。

从图2中可以可以看出，1和4两种情况是对称的，这两种情况的旋转算法是⼀致的，只需要经过⼀次旋转就可以达到⽬标，我们称之为单旋转。2和3两种情况也是对称的，这两种情况的旋转算法也是⼀致的，需要进⾏两次旋转，我们称之为双旋转。

2.2.2 单旋转

单旋转是针对于左左和右右这两种情况的解决⽅案，这两种情况是对称的，只要解决了左左这种情况，右右就很好办了。图3是左左情况的解决⽅案，节点k2不满⾜平衡特性，因为它的左⼦树k1⽐右⼦树Z深2层，⽽且k1⼦树中，更深的⼀层的是k1的左⼦树X⼦树，所以属于左左情况。

为使树恢复平衡，我们把k2变成这棵树的根节点，因为k2⼤于k1，把k2置于k1的右⼦树上，⽽原本在k1右⼦树的Y⼤于k1，⼩于k2，就把Y置于k2的左⼦树上，这样既满⾜了⼆叉查找树的性质，⼜满⾜了平衡⼆叉树的性质。

这样的操作只需要⼀部分指针改变，结果我们得到另外⼀颗⼆叉查找树，它是⼀棵AVL树，因为X向上⼀移动了⼀层，Y还停留在原来的层⾯上，Z向下移动了⼀层。整棵树的新⾼度和之前没有在左⼦树上插⼊的⾼度相同，插⼊操作使得X⾼度⻓⾼了。因此，由于这颗⼦树⾼度没有变化，所以通往根节点的路径就不需要继续旋转了。

2.2.3 双旋转

双旋转：对于左右和右左这两种情况，单旋转不能使它达到⼀个平衡状态，要经过两次旋转。双旋转是针对于这两种情况的解决⽅案，同样的，这样两种情况也是对称的，只要解决了左右这种情况，右左就很好办了。图4是左右情况的解决⽅案，节点k3不满⾜平衡特性，因为它的左⼦树k1⽐右⼦树Z深2层，⽽且k1⼦树中，更深的⼀层的是k1的右⼦树k2⼦树，所以属于左右情况。

为使树恢复平衡，我们需要进⾏两步，第⼀步，把k1作为根，进⾏⼀次右右旋转，旋转之后就变成了左左情况，所以第⼆步再进⾏⼀次左左旋转，最后得到了⼀棵以k2为根的平衡⼆叉树树。

三、构建过程

下⾯是由[1,2,3,4,5,6,7,10,9]构建平衡⼆叉树

数据结构与算法（6）：B树、B+树

具体讲解之前，有⼀点，再次强调下：B-树，即为B树。因为B树的原英⽂名称为B-tree，⽽国内很多⼈喜欢把B-tree译作B-树，其实，这是个⾮常不好的直译，很容易让⼈产⽣误解。如⼈们可能会以为B-树是⼀种树，⽽B树⼜是⼀种树。⽽事实上是，B-tree就是指的B树。特此说明。

⼀、B树

B树（B-tree）是⼀种树状数据结构，能够⽤来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插⼊数据及删除的动作，都在对数时间内完成。B树，概括来说是⼀个⼀般化的⼆叉查找树，可以拥有多于2个⼦节点。与⾃平衡⼆叉查找树不同，B-树为系统最优化⼤块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从⽽加快存取速度。这种数据结构常被应⽤在数据库和⽂件系统的实作上。在B树中查找给定关键字的⽅法是，⾸先把根结点取来，在根结点所包含的关键字K1,…,Kn查找给定的关键字（可⽤顺序查找或⼆分查找法），若找到等于给定值的关键字，则查找成功；否则，⼀定可以确定要查找的关键字在Ki与Ki+1之间，Pi为指向⼦树根节点的指针，此时取指针Pi所指的结点继续查找，直⾄找到，或指针Pi为空时查找失败。

B树作为⼀种多路搜索树（并不是⼆叉的）：

• 定义任意⾮叶⼦结点最多只有M个⼉⼦；且M>2；

• 根结点的⼉⼦数为[2, M]；

• 除根结点以外的⾮叶⼦结点的⼉⼦数为[M/2, M]；

• 每个结点存放⾄少M/2-1（取上整）和⾄多M-1个关键字；

• (⾄少2个关键字）⾮叶⼦结点的关键字个数=指向⼉⼦的指针个数-1；

• ⾮叶⼦结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

• ⾮叶⼦结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字⼩于K[1]的⼦树，P[M]指向关键字⼤于K[M-1]的⼦树，其它P[i]指向关键字属于(K[i-1], K[i])的⼦树；

• 所有叶⼦结点位于同⼀层；

如下图为⼀个M=3的B树示例：

⼆、B+树

B+树是B树的变体，也是⼀种多路搜索树，其定义基本与B-树相同，除了：

1）⾮叶⼦结点的⼦树指针与关键字个数相同；

2）⾮叶⼦结点的⼦树指针P[i]，指向关键字值属于[K[i], K[i+1])的⼦树（B-树是开区间）；

3）为所有叶⼦结点增加⼀个链指针；

4）所有关键字都在叶⼦结点出现；

下图为M=3的B+树的示意图：

B+树的搜索与B树也基本相同，区别是B+树只有达到叶⼦结点才命中（B树可以在⾮叶⼦结点命中），其性能也等价于在关键字全集做⼀次⼆分查找；

B+树的性质：

1.所有关键字都出现在叶⼦结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

2.不可能在⾮叶⼦结点命中；

3.⾮叶⼦结点相当于是叶⼦结点的索引（稀疏索引），叶⼦结点相当于是存储（关键字）数据的数据层；

4.更适合⽂件索引系统。

三、B*树

B∗树是B+树的变体，在B+树的⾮根和⾮叶⼦结点再增加指向兄弟的指针，将结点的最低利⽤率从1/2提⾼到2/3。

B∗树如下图所示：

B*树定义了⾮叶⼦结点关键字个数⾄少为2M/3 ，即块的最低使⽤率为2/3（代替B+树的1/2）；

• B+树的分裂：当⼀个结点满时，分配⼀个新的结点，并将原结点中1/2的数据复制到新结点，最后在⽗结点中增加新结点的指针；B+树的分裂只影响原结点和⽗结点，⽽不会影响兄弟结点，所以它不需要指向兄弟的指针；

• B*树的分裂：当⼀个结点满时，如果它的下⼀个兄弟结点未满，那么将⼀部分数据移到兄弟结点中，再在原结点插⼊关键字，最后修改⽗结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在⽗结点增加新结点的指针；

所以，B∗树分配新结点的概率⽐B+树要低，空间使⽤率更⾼。

数据结构与算法（7）：数据库索引原理及优化

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

⼀、数据结构及算法基础

1.1 索引的本质

MySQL官⽅对索引的定义为：

索引（Index）是帮助MySQL⾼效获取数据的数据结构。提取句⼦主⼲，就可以得到索引的本质：索引是数据结构。

我们知道，数据库查询是数据库的最主要功能之⼀。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的⻆度进⾏优化。最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很⼤时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如⼆分查找（binary search）、⼆叉树查找（binary treesearch）等。

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

看⼀个例⼦：

图1展示了⼀种可能的索引⽅式。左边是数据表，⼀共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是⼀定物理相邻的）。为了加快Col2的查找，可以维护⼀个右边所示的⼆叉查找树，每个节点分别包含索引键值和⼀个指向对应数据记录物理地址的指针，这样就可以运⽤⼆叉查找在O(log2n)O(log2n)的复杂度内获取到相应数据。

虽然这是⼀个货真价实的索引，但是实际的数据库系统⼏乎没有使⽤⼆叉查找树或其进化品种红⿊树（red-black tree）实现的，原因会在下⽂介绍。

1.2 B树和B+树

⽬前⼤部分数据库系统及⽂件系统都采⽤B-Tree或其变种B+Tree作为索引结构，在本⽂的下⼀节会结合存储器原理及计算机存取原理讨论为什么B-Tree和B+Tree在被如此⼴泛⽤于索引，这⼀节先单纯从数据结构⻆度描述它们。要理解B树，必须从⼆叉查找树（Binary search tree）讲起。

⼆叉查找树是⼀种查找效率⾮常⾼的数据结构，它有三个特点。

（1）每个节点最多只有两个⼦树。

（2）左⼦树都为⼩于⽗节点的值，右⼦树都为⼤于⽗节点的值。

（3）在n个节点中找到⽬标值，⼀般只需要log(n)次⽐较。

⼆叉查找树的结构不适合数据库，因为它的查找效率与层数相关。越处在下层的数据，就需要越多次⽐较。它的搜索时间复杂度为O(log2N)，所以它的搜索效率和树的深度有关极端情况下，n个数据需要n次⽐较才能找到⽬标值。对于数据库来说，每进⼊⼀层，就要从硬盘读取⼀次数据，这⾮常致命，因为硬盘的读取时间远远⼤于数据处理时间，数据库读取硬盘的次数越少越好，这⼀点也会在后⾯深⼊剖析。

如果要提⾼查询速度，那么就要降低树的深度。要降低树的深度，很⾃然的⽅法就是采⽤多叉树，再结合平衡⼆叉树的思想，我们可以构建⼀个平衡多叉树结构，然后就可以在上⾯构建平衡多路查找算法，提⾼⼤数据量下的搜索效率

1.2.1 B树

B树（B-tree）是⼀种树状数据结构，能够⽤来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插⼊数据及删除的动作，都在对数时间内完成。B树，概括来说是⼀个⼀般化的⼆叉查找树，可以拥有多于2个⼦节点。与⾃平衡⼆叉查找树不同，B-树为系统最优化⼤块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从⽽加快存取速度。这种数据结构常被应⽤在数据库和⽂件系统的实作上。

在B树中查找给定关键字的⽅法是，⾸先把根结点取来，在根结点所包含的关键字K1,…,Kn查找给定的关键字（可⽤顺序查找或⼆分查找法），若找到等于给定值的关键字，则查找成功；否则，⼀定可以确定要查找的关键字在Ki与Ki+1之间，Pi为指向⼦树根节点的指针，此时取指针Pi所指的结点继续查找，直⾄找到，或指针Pi为空时查找失败。

B树作为⼀种多路搜索树（并不是⼆叉的）：

定义任意⾮叶⼦结点最多只有M个⼉⼦；且M>2；根结点的⼉⼦数为[2, M]；除根结点以外的⾮叶⼦结点的⼉⼦数为[M/2, M]；每个结点存放⾄少M/2-1（取上整）和⾄多M-1个关键字；(⾄少2个关键字）⾮叶⼦结点的关键字个数=指向⼉⼦的指针个数-1；⾮叶⼦结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；⾮叶⼦结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字⼩于K[1]的⼦树，P[M]指向关键字⼤于K[M-1]的⼦树，其它P[i]指向关键字属于(K[i-1], K[i])的⼦树；所有叶⼦结点位于同⼀层；

此外，在B树中，除⾮数据已经填满，否则不会增加新的层。也就是说，B树追求层越少越好

这样的数据结构，⾮常有利于减少读取硬盘的次数。假定⼀个节点可以容纳100个值，那么三层的B树可以容纳100万个数据，但若换成⼆叉查找树，则需要20层！假定操作系统⼀次读取⼀个节点，并且根节点保留在内存中，那么B树在100万个数据中查找⽬标值，只需要读取两次硬盘。

如下图为⼀个M=3的B树示例：

1.2.2 B+树

B+树是B树的变体，MySQL普遍使⽤B+Tree实现其索引结构。也是⼀种多路搜索树，其定义基本与B-树相同，除了：1）⾮叶⼦结点的⼦树指针与关键字个数相同；2）⾮叶⼦结点的⼦树指针P[i]，指向关键字值属于[K[i], K[i+1])的⼦树（B-树是开区间）；3）为所有叶⼦结点增加⼀个链指针；4）所有关键字都在叶⼦结点出现；

下图为M=3的B+树的示意图：

B+树的搜索与B树也基本相同，区别是B+树只有达到叶⼦结点才命中（B树可以在⾮叶⼦结点命中），其性能也等价于在关键字全集做⼀次⼆分查找；

B+树的性质：1.所有关键字都出现在叶⼦结点的链表中（稠密索引），且链表中的关键字恰好是有序的；2.不可能在⾮叶⼦结点命中；1.2.2 B+树3.⾮叶⼦结点相当于是叶⼦结点的索引（稀疏索引），叶⼦结点相当于是存储（关键字）数据的数据层；4.更适合⽂件索引系统。

⼀般在数据库系统或⽂件系统中使⽤的B+ Tree结构都在经典B+ Tree的基础上进⾏了优化，增加了顺序访问指针。做这个优化的⽬的是为了提⾼区间访问的性能，例如下图中如果要查询key为 从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以⼀次性访问到所有数据节点，极⼤提到了区间查询效率。

⼆、计算机组成原理

上⽂说过，红⿊树等数据结构也可以⽤来实现索引，但是⽂件系统及数据库系统普遍采⽤B-/+Tree作为索引结构，这⼀节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

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

2.1 主存存取原理

⽬前计算机使⽤的主存基本都是随机读写存储器（RAM），现代RAM的结构和存取原理比较复杂，这⾥本⽂抛却具体差别，抽象出⼀个⼗分简单的存取模型来说明RAM的⼯作原理。

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

主存的存取过程如下：

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

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

2.2 磁盘存取原理

上⽂说过，索引⼀般以⽂件形式存储在磁盘上，索引检索需要磁盘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毫秒的时间，显然是个灾难。

2.3 局部性原理与磁盘预读

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

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

三、B-/+Tree索引的性能分析

到这⾥终于可以分析为何数据库索引采⽤B-/+Tree存储结构了。上⽂说过数据库索引是存储到磁盘的⽽我们⼜⼀般以使⽤磁盘I/O次数来评价索引结构的优劣。先从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作为索引结构效率是⾮常⾼的。

3.1 B+树性能分析

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

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

3.2 B+树查找过程

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，显然成本⾮常⾮常⾼。

这⼀章从理论⻆度讨论了与索引相关的数据结构与算法问题，下⼀章将讨论B+Tree是如何具体实现为MySQL中索引，同时将结合MyISAM和InnDB存储引擎介绍⾮聚集索引和聚集索引两种不同的索引实现形式。

四、MySQL索引实现

在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现⽅式是不同的，本⽂主要讨论MyISAM和InnoDB两个存储引擎的索引实现⽅式。

4.1 MyISAM索引实现

MyISAM引擎使⽤B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：

这⾥设表⼀共有三列，假设我们以Col1为主键，则上图是⼀个MyISAM表的主索引（Primarykey）示意。可以看出MyISAM的索引⽂件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯⼀的，⽽ᬀ助索引的key可以重复。如果我们在Col2上建⽴⼀个辅助索引，则此索引的结构如下图所示：

同样也是⼀颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为⾸先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引⽅式也叫做“⾮聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

4.2 InnoDB索引实现

虽然InnoDB也使⽤B+Tree作为索引结构，但具体实现⽅式却与MyISAM截然不同。

1）第⼀个重⼤区别是InnoDB的数据⽂件本身就是索引⽂件。

从上⽂知道，MyISAM索引⽂件和数据⽂件是分离的，索引⽂件仅保存数据记录的地址。⽽在InnoDB中，表数据⽂件本身就是按B+Tree组织的⼀个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据⽂件本身就是主索引。

上图是InnoDB主索引（同时也是数据⽂件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据⽂件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会⾃动选择⼀个可以唯⼀标识数据记录的列作为主键，如果不存在这种列，则MySQL⾃动为InnoDB表⽣成⼀个隐含字段作为主键，这个字段⻓度为6个字节，类型为⻓整形。

2）第⼆个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值⽽不是地址。

换句话说，InnoDB的所有辅助索引都引⽤主键作为data域。例如，下图为定义在Col3上的⼀个辅助索引：

这⾥以英⽂字符的ASCII码作为比较准则。聚集索引这种实现⽅式使得按主键的搜索⼗分⾼效，但是辅助索引搜索需要检索两遍索引：⾸先检索辅助索引获得主键，然后⽤主键到主索引中检索获得记录。

了解不同存储引擎的索引实现⽅式对于正确使⽤和优化索引都⾮常有帮助，例如知道了InnoDB的索引实现后，就很容易明⽩为什么不建议使⽤过⻓的字段作为主键，因为所有辅助索引都引⽤主索引，过⻓的主索引会令辅助索引变得过⼤。

再例如，⽤⾮单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据⽂件本身是⼀颗B+Tree，⾮单调的主键会造成在插⼊新记录时数据⽂件为了维持B+Tree的特性⽽频繁的分裂调整，⼗分低效，⽽使⽤⾃增字段作为主键则是⼀个很好的选择。

五、索引使⽤策略及优化

MySQL的优化主要分为结构优化（Scheme optimization）和查询优化（Query optimization）。本章讨论的⾼性能索引策略主要属于结构优化范畴。本章的内容完全基于上⽂的理论基础，实际上⼀旦理解了索引背后的机制，那么选择⾼性能的策略就变成了纯粹的推理，并且可以理解这些策略背后的逻辑。

5.1 联合索引及最左前缀原理

• 联合索引（复合索引）

⾸先介绍⼀下联合索引。联合索引其实很简单，相对于⼀般索引只有⼀个字段，联合索引可以为多个字段创建⼀个索引。它的原理也很简单，⽐如，我们在（a,b,c）字段上创建⼀个联合索引，则索引记录会⾸先按照A字段排序，然后再按照B字段排序然后再是C字段，因此，联合索引的特点就是：

第⼀个字段⼀定是有序的；当第⼀个字段值相等的时候，第⼆个字段⼜是有序的，⽐如下表中当A=2时所有B的值是有序排列的，依次类推，当同⼀个B值得所有C字段是有序排列的

其实联合索引的查找就跟查字典是⼀样的，先根据第⼀个字⺟查，然后再根据第⼆个字⺟查，或者只根据第⼀个字⺟查，但是不能跳过第⼀个字⺟从第⼆个字⺟开始查。这就是所谓的最左前缀原理。

• 最左前缀原理

我们再来详细介绍⼀下联合索引的查询。还是上⾯例⼦，我们在（a,b,c）字段上建了⼀个联合索引，所以这个索引是先按a 再按b 再按c进⾏排列的，所以以下的查询⽅式都可以⽤到索引

上⾯三个查询按照 （a ）, （a，b ）,（a，b，c ）的顺序都可以利⽤到索引，这就是最左前缀匹配。

⽐如：

如果⽤到了最左前缀⽽只是颠倒了顺序，也是可以⽤到索引的，因为mysql查询优化器会判断纠正这条sql语句该以什么样的顺序执⾏效率最⾼，最后才⽣成真正的执⾏计划。但我们还是最好按照索引顺序来查询，这样查询优化器就不⽤重新编译了。

• 前缀索引

除了联合索引之外，对mysql来说其实还有⼀种前缀索引。前缀索引就是⽤列的前缀代替整个列作为索引key，当前缀⻓度合适时，可以做到既使得前缀索引的选择性接近全列索引，同时因为索引key变短⽽减少了索引⽂件的⼤⼩和维护开销。

字符串列(varchar,char,text等)，需要进⾏全字段匹配或者前匹配。也就是=‘xxx’ 或者 like‘xxx%’；字符串本身可能比较⻓，⽽且前⼏个字符就开始不相同。⽐如我们对中国⼈的姓名使⽤前缀索引就没啥意义，因为中国⼈名字都很短，另外对收件地址使⽤前缀索引也不是很实⽤，因为⼀⽅⾯收件地址⼀般都是以XX省开头，也就是说前⼏个字符都是差不多的，⽽且收件地址进⾏检索⼀般都是like ’%xxx%’，不会⽤到前匹配。相反对外国⼈的姓名可以使⽤前缀索引，因为其字符较长，⽽且前⼏个字符的选择性比较⾼。同样电⼦邮件也是⼀个可以使⽤前缀索引的字段。

前⼀半字符的索引选择性就已经接近于全字段的索引选择性。如果整个字段的⻓度为20，索引选择性为0.9，⽽我们对前10个字符建⽴前缀索引其选择性也只有0.5，那么我们需要继续加⼤前缀字符的⻓度，但是这个时候前缀索引的优势已经不明显，没有太⼤的建前缀索引的必要了。

⼀些⽂章中也提到：MySQL 前缀索引能有效减⼩索引⽂件的⼤⼩，提⾼索引的速度。但是前缀索引也有它的坏处：

MySQL 不能在 ORDER BY 或 GROUP BY 中使⽤前缀索引，也不能把它们⽤作覆盖索引(Covering Index)。

5.2 索引优化策略

• 最左前缀匹配原则；

• 主键外检⼀定要建索引；

• 对 where,on,group by,order by 中出现的列使⽤索引；

• 尽量选择区分度⾼的列作为索引,区分度的公式是count(distinct col)/count(*)，表示字段不重复的⽐例，⽐例越⼤我们扫描的记录数越少，唯⼀键的区分度是1，⽽⼀些状态、性别字段可能在⼤数据⾯前区分度就是0；

• 对较⼩的数据列使⽤索引,这样会使索引⽂件更⼩,同时内存中也可以装载更多的索引键；

• 索引列不能参与计算，保持列“⼲净”，⽐如from_unixtime(create_time) = ’2014-05-29’就不能使⽤到索引，原因很简单，b+树中存的都是数据表中的字段值，但进⾏检索时，需要把所有元素都应⽤函数才能比较，显然成本太⼤。所以语句应该写成create_time =unix_timestamp(’2014-05-29’);

• 为较长的字符串使⽤前缀索引尽量的扩展索引，不要新建索引。⽐如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可；

• 不要过多创建索引, 权衡索引个数与DML之间关系，DML也就是插⼊、删除数据操作。这⾥需要权衡⼀个问题，建⽴索引的⽬的是为了提⾼查询效率的，但建⽴的索引过多，会影响插⼊、删除数据的速度，因为我们修改的表数据，索引也需要进⾏调整重建；

• 对于like查询，”%”不要放在前⾯。

  

• 查询where条件数据类型不匹配也⽆法使⽤索引；

• 字符串与数字比较不使⽤索引;
  

  

• 正则表达式不使⽤索引,这应该很好理解,所以为什么在SQL中很难看到regexp关键字的原因