第十章：第1节 MySQL进阶篇——索引是一种数据结构

重点提示：

楠神认为这一章将是我们整个PHP学习最重要的一个章节。

MySQL基础篇，我们只是去学习了要怎么使用MySQL。而这一章进阶篇我们会更加深入了解MySQL，去研究下它底层的一些东西和原理，从而去更好地使用MySQL。

MySQL是PHP开发中最重要的环节，也是一个项目性能、数据最容易出现问题的瓶颈之处。现在PHP面试，都是把数据库或者Linux服务器当做重点来问，面试官是不会只问你PHP语法的问题的，这些东西考察不出一个程序员的水平。或者说，MySQL回答的有水平，那就足以衡量出面试者有一定的工作经验了（没有工作经验MySQL也不好蒙，懂的人一问就露馅），确实有水平能用PHP开发东西。

所以，希望大家要认真地解读这一章节的内容，楠神也尽量去收集最重要的最急需补充的一些知识。都是些原理性的东西可能会难理解和乏味，但如果你能很好地理解和吸收，那对你学习PHP将是大大地一次提高。

先来逐步地探讨MySQL最重要的一个话题——索引。

前面介绍索引犹如字典的目录。

数据库查询是数据库的主要功能之一，最基本的查询算法是顺序查找（linear search）时间复杂度为O(n)，显然在数据量很大时效率很低。优化的查找算法如二分查找（binary search）、二叉树查找（binary tree search）等，虽然查找效率提高了。但是各自对检索的数据都有要求：二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将表的两个字段的数据都按顺序进行组织）。所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构。这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构就是索引。

索引的本质

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是一种数据结构。

用Navicat在一张数据表-》鼠标右键-》设计表-》索引

点击表的索引方式，可以有两个选项：BTREE和HASH。索引是一种数据结构，它可以是BTREE结构，也可以是HASH结构。这两种结构的索引到底用哪个好？这还得需要我们一步一步去分析。HASH我们在第八章讲过，哈希表查东西超级快，可MySQL用得最多的还是BTREE索引。

看一个例子：

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

虽然这是一个货真价实的索引，但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black tree）实现的。目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构，在这篇文章里介绍了原因《为什么B-Tree和B+Tree被广泛用于索引？》。有兴趣的朋友尽量去读一下，有助于我们理解BTREE是怎样的数据结构，对我们以后正确使用索引会有帮助的。