索引对于数据库来说是核心部件，对于索引我们大部分人会有一些粗浅的认识：
索引可以帮助数据库快速定位数据。
索引可以帮助数据库快速提取数据。
索引尽管可以加速数据的提取，但却增加了写入开销，因为你在更新数据的同时，也需要更新索引。
维护索引是DBA最主要的工作之一。
更进一步来说：
针对数据库的内容做全文检索也需要索引，但那是完全不同类型的索引，这跟搜索引擎类似。
索引更新可以是批处理模式，而不一定是实时更新。实际上批处理更新索引也是Google早期发明MapReduce的最早动机之一。
实时更新的索引通常会在批处理阶段进行清理，最著名的例子比如B-Tree的rebalance以及LSM-Tree的merge。
针对OLTP和OLAP的数据库需要不同的技术，以我们最常用的OLTP来说，就存在着各种各样的索引技术，它们之间各有优缺点，然而，好的索引却未必会被主流的数据库尤其是开源产品所采用，例如：
Tokutek，做为在HDD磁盘下能够达到的读写最佳Trade-off，只是在近期被Percona收购之后，才有可能逐步走向MySQL的主流引擎。
MemSQL，做为最快的内存OLTP之一（近期发布的MemSQL 4.0也宣称支持OLAP），在实现中，必须采用无锁数据结构以确保多核上的可伸缩性，然而他们只实现了SkipList，这并不是说SkipList就是最优选择，而是因为基于SkipList实现无锁最容易。
SolidDB，做为IBM的产品，索引构建在Patricia trie上，专门为内存查询优化，但仍然提供内存和磁盘的混合存储。McObject和ScaleDB也尝试了类似的方法，然而几乎没有主流产品注意到这种技术。
一个成熟的数据库系统会采用多种索引技术的组合来优化性能。最好的例子比如曾经的Sybase IQ，它的位图索引技术之后被广泛采用，其实Sybase IQ一共采用了多达9种的不同索引，这正说明了不同的索引都只适用于不同的情况，良好的设计应当需要聪明的判断来决定如何在这些技术之间进行切换。
近8年来，NoSQL引爆开源社区，其实绝大多数NoSQL本质上就是把OLTP的索引拿过来直接当数据存储引擎来使用，因此不论它们鼓吹的性能多么优秀，都是针对某一特定场景下的优化而已，对于各种场景下的查询组合，开源NoSQL社区距离商用产品的确具有不小的差距。
对于OLAP数据库来说，索引则完全是不同的境遇：
OLAP厂商从来都是对索引反感的。例如，最著名的OLAP厂商Netezza根本就不用任何索引（关心广告的同学应当听说过AppNexus，正是采用Netezza来服务它复杂的报表分析dashboard）。列存仓库Vertica也没有用索引，而且Oracle数据仓库（非数据库）也用了很少的索引。它们之所以这样选择的原因是避免索引占用过大的体积，以及避免给DBA带来过高的维护成本，因此通常采用顺序暴力扫描。事实上，随着Google BigQuery的鼓吹，这种不采用索引而暴力扫描数据的作风已经被充分扩散到了开源社区，例如Impala，Drill，Tez，Presto，乃至Spark SQL，无一避免的都是暴力扫描。
然而索引中经常运用的一些技术，会帮助到OLAP的实现者们。例如在实际运用中，很多数据结构会返回超过你所需要的数据，一个最简单的例子是一个磁盘页面上的数据会全部被返回，而不管你是否全部需要它。Netezza采用了一种简单的"Zone Map"的技术来避免完全的暴力扫描，我们可以看作是索引技术的变种。
近期看到的Druid是一个小清新的OLAP——尽管功能弱到其实不能称作为OLAP。由于索引技术和pre-computing的大量运用，使得查询性能要优于暴力扫描OLAP。整体上过滤和分组都采用了位图索引，并且在最新的版本里引入了Roaring压缩位图，这是求交以及求和的最快实现（我们团队成员曾贡献了社区唯一的C++版本实现）。
索引技术是个大坑，针对内存和磁盘，以及SSD分别都有很多不同考虑，本公众号会不定期的针对一些不为人所熟知的索引技术分析。构建索引所需要的两大要素，IO模型和算法，我们首先从前者开始逐步涉及。
谈到IO模型，我们不得不提到一篇重要的文章，是Varnish的作者在2006年撰写的"What's wrong with 1975 programming"。Varnish是一个高性能CDN缓存，作者在架构时完全借鉴了操作系统本身的虚拟内存而没有另外造轮子。那么为什么要惯以1975年编程的标题呢？1975年的计算机具备两种存储，随机访问的内存和辅助存储如卡带和硬盘。1975年的程序需要你告诉它能够使用的 RAM 和磁盘空间。然后它会花费大把的时间来跟踪哪些 对象在 RAM 中和哪些在磁盘中，并根据传输的运作模式来回移动它们。而事实上当今的计算机只有一种存储系统，它通常是某类存储，操作系统和虚拟内存管理硬件将 RAM 转换成这类存储的缓存。
做为对比，Squid，同样一个CDN缓存，采用1975年风格的设计，是这样工作的：Squid 在“RAM”中创建了一个 HTTP 对象，接着很快就被使用了几次。一段时间后它没有再被命中过且内核注意到了这点。然后某人因为某些用途尝试向内核获取内存，内核便决定将内存中那些没有使用到的页面拉出到交换空间。但这是在 Squid 毫不知情的情况下发生的，一段时间后，Squid 也会注意到这些对象是没用的，并打算将它们转移到磁盘中，以让空出来的 RAM 可用于更频繁被用到的数据。Squid 便出来创建一个文件，然后将这个 HTTP 对象写入这个文件。现在我们切换到慢速回放：Squid 调用 write，我所提供的地址是一个“虚拟地址”，内核已经将其标志为“不在物理内存中，已被转移到交换空间”。所以 CPU 硬件分页单元会发出一个软中断（trap），操作系统中所谓的中断就会告诉它“请恢复一下内存”。内核尝试寻找一个空闲的页面，如果没有，它会拿将某个不怎么使用的页面，很可能是另一个很少使用的 Squid 对象，将写入到磁盘上的页面池（交换空间）。当那些写入完成后，它会从页面池的另一个数据被分页出去的地方读入到现在不使用的 RAM 页面，再修改分页表，并重试刚执行失败的指令。Squid 对此一无所知，对 Squid 而言这只是一次常规的内存访问罢了。所以现在 Squid 让这个对象出现在内存中的页面上，还将其写到磁盘上，这就出现了两个副本：一个在操作系统的页面空间里，另一个在文件系统中。Squid 现在将这段 RAM 作其他用途，但一段时间后，这个 HTTP 对象被命中了，所以 Squid 需要将它取出来。首先，Squid 需要得到一些 RAM，因此可能打算将其他 HTTP 对象放到磁盘上（重复上述的步骤），然后从文件系统的文件中读入这个 HTTP 对象，再然后向网络连接套接字发送这个 HTTP 对象的数据。这听起来是不是在给你做无用功啊？
这是 Varnish 的做法：Varnish 先分配一些虚拟内存，并告知操作系统将这段内存备份到磁盘上的一个文件的存储空间中。当需要向客户端发送对象时，它只要提交那块虚拟内存空间，剩下的就交给内核即可。如果/当内核认为它需要 RAM 作其他用途时，那个页面会被写到后备文件并将这段 RAM 用于其他地方。 当 Varnish 下次提交这段虚拟内存时，操作系统会查找一个 RAM 页面，也可能会释放一个，并从后备文件中读入其内容。仅此而已。Varnish 并不会去控制哪些内容缓存在 RAM 中或哪些不是，内核代码和硬件维护程序会处理好这些事情，并且的确处理好了。Varnish 也只是使用了一个磁盘文件，而 Squid 却将每个对象放到各自独立的文件中。HTTP 对象不需要像文件系统对象那样，所以对于每个对象都在文件系统命名空间（目录、文件名和诸如此类的东西）上浪费时间没有任何意义，在 Varnish 中所需要的就是一个虚拟内存的指针和一个长度值，剩下的就是内核的事了。虚拟内存就是为了在实际数据量大于物理内存容量的时候让编程变得更容易而出现的，而人们却仍然不明白。
对比Varnish和Squid，Redis的设计者antirez就曾经在2011年犯下类似的错误。这个设计动机很简单：想让 Redis 可以服务整体数据集大于内存，但热点数据集小于内存的场景，为此发明了"Redis Virtual Memory"，antirez并且撰写了"What's wrong with 2006 programming"来和上面的1975年编程针锋相对。事实上，antirez的文章也有足够充足的理由：当某页数据实际处在硬盘上时，当前请求的线程就需要阻塞等待该页被载入内存。这对于 Redis 的单线程模型来说是致命的，而自主的虚拟内存设计使得 Redis 则可以在保持主处理逻辑单线程的情况下在虚拟内存逻辑部分引入线程池来避免全局阻塞。尽管如此，虚拟内存的设计在 Redis 2.4 版本后还是废弃了，已经消失在Redis代码库中，主要原因还是缺乏实用性和增加了过多的复杂度。
很多工作都受益于1975编程这篇文章，例如3.0版之前的MongoDB，LMDB，MDBM，NLDB，等等，都是直接采用虚拟内存提供存储引擎而程序本身只专注事务处理，特别是后几种嵌入式索引都达到了百万以上的TPS，性能非常优良。连时间序列数据库的主导之一InfluxDB也都在最新版本中切换到一个叫BoltDB的直接基于虚拟内存的存储引擎。然而，这里边所提到的所有数据库以及索引实现，都是比较简单的把所有工作丢给虚拟内存处理，这在机器独占，并且热点数据少于可用内存的情况下表现优良，其他情况下，就很难说是最优选择了。
现代数据库索引技术是算法跟IO的组合体，算法是基于IO推衍，所有的一切算法设计，都是为了降低IO开销，提高cache（内存和指令）命中率，从cache concious tree到cache oblivous design，无不是基于此，在后边的系列文章中，我们会选择性的针对若干优秀设计进行分析。
