本文摘自PHP中文网，作者coldplay.xixi，侵删。
今天MySQL数据库栏目介绍MySQL索引与ElasticSearch索引的对比。
前言
这段时间在维护产品的搜索功能，每次在管理台看到 elasticsearch 这么高效的查询效率我都很好奇他是如何做到的。
这甚至比在我本地使用 MySQL 通过主键的查询速度还快。
为此我搜索了相关资料：
这类问题网上很多答案，大概意思呢如下：
- ES 是基于
Lucene的全文检索引擎，它会对数据进行分词后保存索引，擅长管理大量的索引数据，相对于MySQL来说不擅长经常更新数据及关联查询。
说的不是很透彻，没有解析相关的原理；不过既然反复提到了索引，那我们就从索引的角度来对比下两者的差异。
MySQL 索引
先从 MySQL 说起，索引这个词想必大家也是烂熟于心，通常存在于一些查询的场景，是典型的空间换时间的案例。
1 |
|
常见的数据结构
假设由我们自己来设计 MySQL 的索引，大概会有哪些选择呢？
散列表
首先我们应当想到的是散列表，这是一个非常常见且高效的查询、写入的数据结构，对应到 Java 中就是 HashMap
这个数据结构应该不需要过多介绍了，它的写入效率很高O(1),比如我们要查询 id=3 的数据时，需要将 3 进行哈希运算，然后再这个数组中找到对应的位置即可。
但如果我们想查询 1≤id≤6 这样的区间数据时，散列表就不能很好的满足了，由于它是无序的，所以得将所有数据遍历一遍才能知道哪些数据属于这个区间。
有序数组
有序数组的查询效率也很高，当我们要查询 id=4 的数据时，只需要通过二分查找也能高效定位到数据O(logn)。
同时由于数据也是有序的，所以自然也能支持区间查询；这么看来有序数组适合用做索引咯?
自然是不行，它有另一个重大问题；假设我们插入了 id=2.5 的数据，就得同时将后续的所有数据都移动一位，这个写入效率就会变得非常低。
平衡二叉树
既然有序数组的写入效率不高，那我们就来看看写入效率高的，很容易就能想到二叉树；这里我们以平衡二叉树为例：
由于平衡二叉树的特性：
左节点小于父节点、右节点大于父节点。
所以假设我们要查询 id=11 的数据，只需要查询 10―>12―>11 便能最终找到数据，时间复杂度为O(logn)，同理写入数据时也为O(logn)。
但依然不能很好的支持区间范围查找，假设我们要查询5≤id≤20 的数据时，需要先查询10节点的左子树再查询10节点的右子树最终才能查询到所有数据。
导致这样的查询效率并不高。
跳表
跳表可能不像上边提到的散列表、有序数组、二叉树那样日常见的比较多，但其实 Redis 中的 sort set 就采用了跳表实现。
这里我们简单介绍下跳表实现的数据结构有何优势。
我们都知道即便是对一个有序链表进行查询效率也不高，由于它不能使用数组下标进行二分查找，所以时间复杂度是o(n)
但我们也可以巧妙的优化链表来变相的实现二分查找，如下图：
我们可以为最底层的数据提取出一级索引、二级索引，根据数据量的不同，我们可以提取出 N 级索引。
当我们查询时便可以利用这里的索引变相的实现了二分查找。
假设现在要查询 id=13 的数据，只需要遍历 1―>7―>10―>13 四个节点便可以查询到数据，当数越多时，效率提升会更明显。
同时区间查询也是支持，和刚才的查询单个节点类似，只需要查询到起始节点，然后依次往后遍历（链表有序）到目标节点便能将整个范围的数据查询出来。
同时由于我们在索引上不会存储真正的数据，只是存放一个指针，相对于最底层存放数据的链表来说占用的空间便可以忽略不计了。
平衡二叉树的优化
但其实 MySQL 中的 Innodb 并没有采用跳表，而是使用的一个叫做 B+ 树的数据结构。
这个数据结构不像是二叉树那样大学老师当做基础数据结构经常讲到，由于这类数据结构都是在实际工程中根据需求场景在基础数据结构中演化而来。
比如这里的 B+ 树就可以认为是由平衡二叉树演化而来。
刚才我们提到二叉树的区间查询效率不高，针对这一点便可进行优化：
在原有二叉树的基础上优化后：所有的非叶子都不存放数据，只是作为叶子节点的索引，数据全部都存放在叶子节点。
这样所有叶子节点的数据都是有序存放的，便能很好的支持区间查询。
只需要先通过查询到起始节点的位置，然后在叶子节点中依次往后遍历即可。
当数据量巨大时，很明显索引文件是不能存放于内存中，虽然速度很快但消耗的资源也不小；所以 MySQL 会将索引文件直接存放于磁盘中。
这点和后文提到 elasticsearch 的索引略有不同。
由于索引存放于磁盘中，所以我们要尽可能的减少与磁盘的 IO（磁盘 IO 的效率与内存不在一个数量级）
通过上图可以看出，我们要查询一条数据至少得进行 4 次IO，很明显这个 IO 次数是与树的高度密切相关的，树的高度越低 IO 次数就会越少，同时性能也会越好。
相关阅读 >>
更多相关阅读请进入《MySQL索引》频道 >>
数据库系统概念 第6版
本书主要讲述了数据模型、基于对象的数据库和XML、数据存储和查询、事务管理、体系结构等方面的内容。
