我们来一下世界上最简单的数据库，它用两个Bash功能实现：
#!/bin/bash
db_set () {
echo "$1,$2" >> database
}
db_get () {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}
这两个函数实现键值存储。你可以调用db_set key value，它会在数据库中存储键和值。键和值可以是（几乎）任何您喜欢的东西——例如，值可以是一个JSON文档。然后您可以调用dbget key，它查找与该键关联的最新值并返回它。
它的工作示例如下:
$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}'
$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
底层存储格式非常简单：一个文本文件，其中每一行包含一个键-值对，用逗号分隔（大致类似于CSV文件，忽略转义问题）。每次调用db_set附加到文件的末尾，所以如果你更新一个键几次,老版本的值不会覆盖-你需要在文件中找到最后一次存储的键来找到最新的值(类似tail- n 1 db_get)：
$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}
$ cat database
123456,{"name":"London","attractions":["Big Ben","London Eye"]}
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}
我们的dbset函数实际上在非常简单的事情上有很好的性能，因为追加到一个文件通常是非常有效的。与dbset所做的类似，许多数据库在内部使用日志，这是一个只允许追加的数据文件。真正的数据库有更多的问题需要处理（比如并发控制、回收磁盘空间来让日志不会永远增长，处理错误和部分文字记录），但是基本原理是一样的。日志是非常有用的，我们将在以后的其余部分中多次遇到它们。
另一方面，如果您的数据库中有大量的记录，那么我们的dbget函数的性能就很糟糕。每次您想要查找一个键时，dbget必须从头到尾扫描整个数据库文件，寻找键的出现。在算法的术语中，查找的成本是O(n)：如果您将数据库中记录n的数量增加一倍，那么查找的花费是它的两倍。这并不优秀。
为了有效地找到数据库中特定键的值，我们需要一个不同的数据结构：一个索引。在这一章中，我们将研究一系列的索引结构，看看它们是如何比较的；它们背后的基本思想是在侧面保留一些额外的元数据，它充当路标，帮助您定位您想要的数据。如果您想以几种不同的方式搜索相同的数据，那么您可能需要在数据的不同部分上使用几个不同的索引。
索引是由原始数据派生的另一种结构。许多数据库允许您添加和删除索引，这不会影响数据库的内容；它只会影响查询的性能。维护额外的结构会导致开销，特别是在写操作上。对于写操作来说，很难超越简单地追加到一个文件的性能，因为这是最简单的写操作。任何类型的索引通常会减慢写操作的速度，因为索引还需要在每次数据写入时更新。
这在存储系统中是一个重要的权衡：精心选择的索引加快了读取查询，但是每个索引都减慢了写操作的速度。出于这个原因，数据库通常不会在默认情况下对所有内容进行索引，但是需要你——应用程序开发人员或数据库管理员——使用你对应用程序典型查询模式的知识来手动选择索引。然后，你可以选择给应用程序带来最大好处的索引，而不需要引入更多的开销。
哈希索引
让我们从键值数据的索引开始。这不是你可以索引的唯一类型的数据，但它非常常见，而且对于更复杂的索引来说，它是一个有用的构建块。
键值存储与你在大多数编程语言中找到的字典类型非常相似，并且通常作为散列映射（哈希表）实现。哈希映射在许多算法教科书中都有描述，所以我们不会详细说明它们是如何工作的。既然我们已经有了内存数据结构的散列映射，为什么不使用它们来在磁盘上索引我们的数据呢？
假设我们的数据存储只包含到一个文件中，就像前面的例子一样。然后，最简单的索引策略是：保留一个内存中的哈希映射表，其中每个键都映射到数据文件中的字节偏移——可以找到值的位置，如图3-1所示。每当您向文件追加一个新的键-值对时，您也会更新哈希映射，以反映您刚才所写的数据的偏移量（这既适用于插入新键，也适用于更新现有键）。当你想要查找一个值时，使用哈希映射来找到数据文件中的偏移量，寻找那个位置，并读取值。
网友评论