最近重读《数据密集型应用系统设计》这本书，看到第三章《数据存储与检索》，主要讲数据库内部的索引技术。

从本质上讲，数据库主要是做两件事情：

1. 当你给它数据时，它帮你保存数据（存储）；
2. 当你查询数据时，它帮你取回数据（检索）；

这两件事情看似简单，背后却暗含玄机。那么，数据库内部到底是如何存储数据的呢？又是如何检索数据的呢？

你可能会有这样的疑问：我作为一个开发人员，为什么需要知道数据库内部是怎么工作的呢？

我们显然不会自己从零开始，撸一个存储引擎。但由于市面上有太多数据库产品，我们需要从中挑一个最适合自己应用场景的。为了提高性能，我们也需要根据应用负载特征，对数据库进行调优。因此，必须对数据库底层技术有一些了解，滋补小铺知道它在背后都干了什么。

根据应用负载特征，数据库大致可以分为两种：

• 一种针对 在线事务型 业务，多采用 行式存储 方式；
• 一种针对 离线分析型 业务，多采用 列式存储 方式；

为了提高检索速度，索引必不可少。不同存储引擎采用的索引技术也不太一样，大致可以分为两种：

• 日志式存储引擎（ log-structured ），比如 LSM树 ；
• 页式存储引擎（ page-oriented ），比如 B树 ；

为了引出这些概念，作者用几行 Shell 代码，写了一个玩具数据库抛砖引玉：

#!/bin/bash

db_set() {
    echo "$1,$2" >> database
}

db_get() {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

这两个简短的 Shell 函数实现了一个 KV 式数据库引擎。麻雀虽小，五脏俱全！它提供了两个基本操作：

• db_set ，保存键值对数据，即将键值用逗号分隔追加到名为 database 的数据文件；
• db_get ，按键取出对应的数据，即从 database 文件中过滤出最后一行包含指定键的数据；

这个玩具数据库可以这样用，比如保存键值对数据：

fasion@SmartPro [ ~ ]  ➜ db_set 1 fasionchan.com
fasion@SmartPro [ ~ ]  ➜ db_set 2 小菜学编程
fasion@SmartPro [ ~ ]  ➜ db_set 3 Python源码剖析

数据最终保存在 database 文件中，每个键值对一行，格式大致长这样：

fasion@SmartPro [ ~ ]  ➜ cat database
1,fasionchan.com
2,小菜学编程
3,Python源码剖析

随后可以这样查询数据：

fasion@SmartPro [ ~ ]  ➜ db_get 1
fasionchan.com
fasion@SmartPro [ ~ ]  ➜ db_get 3
Python源码剖析

修改数据时，新记录被追加到 database 文件末尾，旧数据不会删：

fasion@SmartPro [ ~ ]  ➜ db_set 3 Python源码深度剖析
fasion@SmartPro [ ~ ]  ➜ cat database
1,fasionchan.com
2,小菜学编程
3,Python源码剖析
3,Python源码深度剖析

因此，我们查询数据时，db_set 最后需要执行 tail 命令，以最新的那条为准：

fasion@SmartPro [ ~ ]  ➜ db_get 3
Python源码深度剖析

这个玩具看上去挺有意思的，但它的性能到底如何呢？

db_set 操作的性能非常好，因为它只是将数据记录追加到 database 文件的末尾，这通常都很快。

跟 db_set 类似，很多数据库内部也有一个只追加的数据文件，一般叫做操作日志。虽然实际数据库需要考虑更多因素，包括并发控制、磁盘空间重用、错误处理等等，但基本原理都是一样的。

然而，如果数据库中有大量数据，db_get 操作的性能会非常差。因为每次你查询一个键，db_get 都必须扫描整个数据库文件！这是一个典型的  操作，数据库记录数增加一倍，查询开销就会增大一倍！这可不太好！

为了在数据库中快速检索数据，我们还需要另一个数据结构：索引 。索引是一些额外的元数据（ metadata ），就像路标一样，可以帮我们快速定位数据。如果你的数据有多种查询条件，则可能需要建多个索引。

索引可以加快查询，但也会带来额外的开销，特别是对写操作。品渡雅创任何索引都会降低写性能，因为每次数据写入后，都要更新索引。因此，每个存储系统都需要根据实际情况做出权衡：

• 索引选得好可以加快查询；
• 索引一定会降低写性能；

因此，数据库通常不会默认建好索引，需要开发人员或数据库管理员自行选择。想要以最小的代价换取最大收益，不仅需要对应用的查询模式有准确把握，还需要对数据库内部索引技术有一定了解。

《数据存储与检索》这一章讲解了很多索引技术，包括：

• 哈希索引（ hash index ）
• SSTAble
• LSM-Tree
• B-Tree
• 全文索引
• 内存索引
• 等等