这可能是世界上最简单的数据库了，它由两个Bash函数组成：

这两个函数实现了键值存储。你可以通过db_set key value的形式将键值存储去数据库。这里的键值可以是你能想到的任何事物，比如说value值可以是一个JSON文档。你可以通过db_get key的形式，查找与该特定key关联的最新值键并返回它。并且如下工作：

基本的存储格式非常简单：一个文本文件，其中每行包含一个键值对，并用逗号分隔（大致类似于CSV文件，而忽略转义问题）。

每次对db_set的调用都会追加到文件的末尾，因此，如果多次更新键，则该值的旧版本不会被覆盖-您需要查看文件中键的最后一次出现以找到最新值（因此db_get中的tail -n 1）：

函数db_set的性能相当不错，因为它简单并且在文件尾部附加内容一般而言是非常高效的。类似于db_set，许多数据库在其内部使用一个仅追加数据的文件,名为log日志。真实的数据库有更多的问题需要处理，诸如并发控制，回收磁盘空间，以使日志log不会永远增长，处理错误和部分地写入的记录，但最基本的原则是一样的，日志相当有用。

另外一个方面，如果在你的数据库中有大量的记录，那么我们的db_get函数的性能是很糟糕的。每次你想查找一个key，db_get都会从头至尾扫描整个数据库，查找key的出现次数。从算法上看，最糟糕的查找是O(n)，如果你的数据库记录是扩大了原本记录量的两倍，那么查找也将花费两倍的时间。这太糟糕了。

为了在数据库里高效的查找指定key的value，我们需要一个不一样的数据结构：一个index索引。这背后的含义是：在边上保有一些额外的元数据，用来充当路标来帮助我们定位你想要的数据。如果要以几种不同的方式搜索相同的数据，则可能需要在数据的不同部分使用多个不同的索引。

索引是从主要数据派生的附加结构。许多数据库允许你增加和移除索引，并且这不会影响数据库中的内容，它只会影响查找的性能。维护额外的附加结构的开销是很大的，尤其是写操作。对于写操作来说，很难超越仅附加到文件末尾的性能表现，因为这是最简单的写操作。任何类型的索引通常都会减缓写入速度，因为每次写数据都要更新索引。

这是存储系统的一个很重要的折中：精心选择的索引可以加快读取查询的速度，但是每个索引都会减缓写入速度。因此数据库默认情况下不会为所有内容建立索引，而是需要应用开发人员或数据库管理员，根据对应用的一般查询模式的了解，手动地挑选索引。从而你可以选择使您的应用程序受益最大的索引，而不会引入不必要的开销。

哈希索引Hash Indexes

让我们从针对键值数据的索引开始。这不是你能建立索引的唯一一种类型的数据，但是非常常见，对于更复杂的索引，它是一个有用的构建块。

键值存储与你在大多数编程语言里所看到的dictionary字典类型（通常使用hash map哈希映射/hash table哈希表实现）非常相似。哈希映射在许多算法书籍中都有提及，这里我们就不展开了。由于我们已经为内存中的数据结构提供了哈希映射，为什么不使用它们，在磁盘上索引我们的数据呢？

假设我们的数据存储仅包括附加到文件中，如上例所示。那么最简单的索引策略是：在内存中的保持一个哈希映射，其中每个key都映射到数据文件中的字节偏移量（可以找到该值的位置），如下图所示：

这听起来很简单，但这是一种可行的方法。实际上，这就是Bitcask（Riak中的默认存储引擎）所干的事。 Bitcask可以提供高性能的读写功能，但前提是所有key都必须位于可用的RAM中，因为哈希映射完全保留在内存中。可以通过一次磁盘搜索从磁盘中加载value，value可能会比可用内存占用更多?的空间。如果数据文件的一部分已经在文件系统的高速缓存中时，那么一次读取不要任何的磁盘I/O操作。

像Bitcask这样的存储引擎非常适合每个键对应的值频繁更新的状况。比如说，key可能是一段小猫视频的URL，并且value可能是这段视频的播放次数。在这样的工作负载下，虽然有许多的写操作，但没有那么多的不同的键，每个键都会有很多的写操作，但我们在内存中保存所有的key是可行的。

到目前为止，我们只描述了一个可以附加数据记录的文件，那么我们如何避免用尽磁盘空间呢？一个好的解决方案，把日志文件细分成好几个特定大小的段，当到达特定尺寸时，关闭一个段，并且接着写入一个新的段文件。我们可以在对这些段进行compaction压实。压实是指去除日志文件中的重复的key，只保留每个key的最近的被更新的值。如下图：

此外，既然压实一般可以让记录段变得更小（假定一个key在一个段中被重复写了好几次），所以我们可以把执行压实的时候，一次把好几个段压实在一起，如下图。

段在被写入后不再被修改，所以我们是把段合并到一个新的文件中。合并和压缩可以通过一个后台线程完成，这样当它运行时，我们仍然可以使用旧的段文件进行正常的读写。当合并完成后，我们可以把读操作从旧的段文件上切换到新的合并后的文件，然后旧的段文件就可以被删除了。

每个段文件在内存中都有自己的哈希表，用于映射每个key的字节偏移量。为了找到一个key对应的值，我们首先检查最近被使用过的段的哈希映射，如果key不在其中，则检查第二个最近被使用过的段，以此类推。因为压缩合并会使得段的数量变得很小，因此并不会检查很多的哈希映射。

使这个简单的想法在实践中起作用的细节很多。简要地说，在实际实现中重要的问题是：

• 文件格式：CSV不是日志文件的最佳格式。使用二进制格式更快，更简单，该格式首先以字节为单位编码字符串的长度，然后以原始字符串（无需转义）存储日志记录。
• 删除记录：如果你想删除一个key和它相关联的value，你不得不在数据文件中附加一条特殊的删除记录，有时被称为tomebstone墓碑，当日志文件合并时，tomestone会告诉合并过程丢弃关注这个被删除的key之前的任何值。
• 崩溃恢复：如果数据库重启了，那么内存中的哈希映射就丢失了。原则上，您可以通过从头到尾读取整个段文件并记下每个键的偏移量的最新值来恢复每个段的哈希图。然而，如果有段文件很大的话，那会花费很长时间，从而导致服务器的重启变得很痛苦。Bitcask通过在磁盘上存储每隔段的哈希映射的快照（这会加快加载进内存的速度）从而加速恢复。
• 部分写：数据库可能会在任何时候崩溃，其中就包括在日志写入过半时。Bitcask的文件中包含了校验值，这使得日志中损坏的部分可以被删除并且被忽略。
• 并发控制：由于严格按照顺序将写操作追加到日志中，因此常见的实现选择是只有一个写的线程。数据文件段是只能追加的，否则是不可变的，因此可以由多个线程同时读取。

一个只能附加的日志似乎在第一眼看时觉得有点浪费：为什么我们不能在文件中对应key的位置，通过用新的value来覆盖旧的value更新文件呢？原因如下：

• 追加和段合并是顺序写入操作，通常比随机写入要快得多，尤其是在通过磁旋转磁盘的硬盘驱动器上。在某种程度上，顺序写入在基于闪存的固态驱动器（SSD）上也是较好的。
• 如果段文件是只能附加或不可改变的话，那么并发和崩溃恢复会简单的多。比方说，我们不需要担心如下这种情形：当一个value正在被覆盖写时，发生了崩溃，而导致文件各包含了新值和旧值的各一部分。
• 合并旧段可避免随着时间的流逝数据文件碎片化的问题。

然而哈希表索引也有一些限制：

• 哈希表必须能容纳在内存中，因此，如果您有大量的key，那么您将很不走运。原则上，您可以在磁盘上维护哈希表，但是不幸的是，很难使磁盘上的哈希表表现良好。它需要大量的随机访问I / O，在存储满时进行增长的开销是很大很大的，并且哈希冲突需要精巧的逻辑。
• 范围查找并不高效。比方说，你不能简单的搜索在kitty0000到kitty9999之间所有的key，你不得不一个一个的搜索其中的每一个key。