从最基本的层面来说，数据库只需要做两件事：向其中插入数据，它会保存数据，然后在查询时返回这些数据。本文讨论如何存储输入数据，以及当收到查询请求时，如何再次查找数据。为什么要关注数据库内部的存储和检索？你不可能从头实现一个存储引擎，你往往需要从现有的众多存储引擎中选择适合你业务的存储引擎。在针对特定工作负载调整数据库时，有必要了解存储引擎的底层机制。事务工作负载和分析工作负载的存储引擎优化存在很大差异。TransactionProcessingandAnalyticalProcessing”和“Column-OrientedStorage”部分，分析优化存储引擎。首先讨论存储引擎，它被用在两个熟悉的数据库，传统关系数据库和NoSQL数据库。研究两个存储引擎家族，即一个日志结构存储引擎和面向页面的存储引擎，如B-tree数据库核心：数据结构最简单的数据库，由两个Bash函数实现：#!/bin/bashdb_set(){echo"$1,$2">>database}db_get(){grep"^$1,"database|sed-e"s／^$1,//"tail-n1}这两个函数实现了一个K.V的存储，调用db_setkeyvalue时，会保存你在数据中输入的键值键值几乎可以是任何东西。例如，值可以是一个JSON文档。然后调用db_get键，它将查找与输入键关联的最新值并返回它。示例：$db_set123456'{"name":"London","attractions":["BigBen","LondonEye"]}'$db_set42'{"name":"SanFrancisco","attractions":["金门大桥"]}'$db_get42{"name":"SanFrancisco","attractions":["金门大桥"]它的底层存储格式其实很简单：纯文本文件。每行包含一个K.V.逗号分隔（大致类似于csv文件，忽略转义问题）。每次调用db_set时，新内容都会附加到文件末尾。因此，如果某个K多次更新，旧的版本值不会被覆盖，需要查看文件中最后一次出现的K，找到最新的V（所以在db_get中使用tail-n1）。$db_set42'{"name":"SanFrancisco","attractions":["Exploratorium"]}'$db_get42{"name":"SanFrancisco","attractions":["Exploratorium"]}$catdatabase123456,{"name":"London","attractions":["BigBen","LondonEye"]}42,{"name":"SanFrancisco","attractions":["GoldenGateBridge"]}42,{"name":"SanFrancisco","attractions":["Exploratorium"]}在简单的情况下，追加到文件末尾通常足够高效，因此db_set函数具有良好的性能。和db_set类似，很多数据库内部都使用了一个log，这是一个只支持appendupdates的数据文件。虽然真实的数据库有很多更复杂的问题需要考虑（例如并发控制、回收磁盘空间来控制日志文件大小、处理错误和部分完成写入记录等），但基本原理是相同的。日志这个词通常是指应用程序的运行输出日志，记录发生了什么。日志是一个更一般的意思，代表一个只能追加的记录序列集合。它可能不是人类可读的，它可能是二进制格式并且只能由其他程序读取。另一方面，如果日志文件包含大量记录，db_get的性能就会很差。每次要找一个K，db_get都要从头到尾扫描整个数据库文件，找到K的出现。用算法来说，查找成本是O(n)，即如果数据库记录数翻倍，查找需要两倍的时间。不是很好。为了在数据库中高效地找到特定K的V，需要一个数据结构：索引。它们背后的基本思想是保留一些额外的元数据作为路标，以帮助定位所需的数据。如果你想以几种不同的方式搜索相同的数据，你可以在数据的不同部分定义多个不同的索引。索引是从原始数据派生的附加数据结构。许多数据库允许单独添加和删除索引而不影响数据库内容，它只影响查询性能。维护额外的结构必然会引入开销，尤其是在写入新数据时。对于写入器来说，很难超越简单附加文件的性能，因为这已经是最简单的写入操作了。由于每次写入数据都需要更新索引，所以任何类型的索引基本上都会拖慢写入速度。存储系统中一个重要的权衡索引可以加快查询速度，但是每个索引都会减慢写入速度。默认情况下，数据库通常不会索引所有内容，这需要SE或DBA根据对应用程序典型查询模式的了解手动决定索引。就是为应用程序提供最有利的加速，避免引入过多不必要的开销。哈希索引以KV数据的索引开始。KV类型不是唯一可以索引的数据，但它们随处可见，并且是其他更复杂索引的基础。KV存储类似于大多数编程语言内置的字典结构，一般采用hashmap或hashtable来实现。既然内存中的数据结构已经有了hashmaps，那为什么不用它们直接索引磁盘上的数据呢？假设数据存储全部由追加文件组成，最简单的索引策略：将hashmap保存在内存中，将每一个K一一映射到数据文件中特定的字节偏移量，这样每个值的值就可以被发现。位置：图1每当一个新的KV对被添加到文件中时，hashma必须更新以反映刚刚写入的数据的偏移量（包括插入新的K和更新现有的K）。查找值时，使用hashmap查找文件中的偏移量，即存储位置，读取其内容。听起来很简单，但它确实有效。Bitcask（Riak的默认存储引擎）就是这样做的。Bitcask提供了高性能的读写，但是所有的K都必须适合内存。另一方面，V可以使用比可用内存更多的空间。只有一次磁盘寻道可以将V从磁盘加载到内存。如果数据文件的那部分已经在文件系统缓存中，则读取不需要任何磁盘I/O。Bitcask是一种存储引擎，适用于每个K的V更新频繁的场景。如：K，视频的URLV，播放次数（每次有人点击播放按钮递增）在这个workload中，写操作很多，但是不同的K并不多，也就是每个K都有一个很多写操作，但是把所有的K都放在内存中还是可行的。到目前为止，只附加到一个文件，那么如何避免最终耗尽磁盘空间？将日志分成一定大小的段，当达到一定大小时关闭日志文件，开始写入新的段文件。然后可以压缩这些段：图2：压缩KV更新日志文件，只保留每个K的最新值压缩意味着丢弃日志中重复的K，只保留每个K的最新更新。由于压缩往往会使段变小（假设K在一个段中平均被重写多次），所以在执行压缩时也可以合并段：图3：同时执行段压缩并合并多个段，因为段是正在写入的段以后不会被修改，所以合并后的段会写入一个新的文件中。合并和压缩这些冻结段的过程可以在后台线程中完成，在运行时，仍然可以使用旧的段文件继续正常的读写请求。合并过程完成后，将读取请求切换到新的合并段，旧的段文件就可以安全删除了。每个段现在都有自己的内存中哈希表，将K映射到文件中的偏移量。要找到键的值，首先检查哈希图的最新段；如果K不存在，则检查第二个最新的段，依此类推。因为合并过程可以维护少量的段，所以查找通常不需要检查那么多的hashmap。实施难点(1)CSV文件格式不是最好的日志格式，二进制格式更快更简单。先记录字符串的字节长度，然后跟上原来的字符串（不转义）。(2)删除记录要删除一个K及其V，必须在数据文件中添加一条特殊的删除记录（有时称为逻辑删除）。合并日志段时，一旦发现一个墓碑标记，这个删除键的所有值都会被丢弃。(3)崩溃恢复如果数据库重启，内存中的hashmap就会丢失。原则上，可以通过从头到尾读取整个段文件，记录每个键最近值的偏移量来恢复每个段的hashmap。但如果段文件很大，这可能需要很长时间，这会使服务器重启非常慢。Bitcask通过在磁盘上存储每个段的哈希映射的快照来加速恢复，可以更快地将其加载到内存中。(4)部分写入的记录数据库随时可能崩溃，包括在追加记录到日志的过程中。Bitcask文件包含校验和，以便可以找到并丢弃损坏的部分。(5)并发控制由于写入是严格按照顺序追加到日志中的，常见的实现方式是只有一个写入线程。数据文件段是可附加的和不可变的，因此它们可以被多个线程并发读取。附加的日志看起来很浪费：为什么不更新文件，用新值覆盖旧值？AppendWrite设计的优势Appends和段合并是顺序写入，通常比随机写入快得多，尤其是在旋转磁盘上。在某种程度上，顺序写入在基于闪存的固态驱动器(SSD)上也能很好地工作。如果段文件是可追加的或不可变的，并发性和崩溃恢复就简单多了。如果您不必担心重写值时发生崩溃，您将留下一个包含一些旧值和一些新值的混合文件。合并旧段可以避免数据文件随着时间的推移而碎片化。哈希索引的缺点哈希表必须适合内存。如果你有很多钥匙，那你就不走运了。原则上可以在磁盘上维护一个hashmap，但是磁盘上的hashmap很难很好的执行，需要大量的随机访问I/O。当hash变满后，继续增长代价高昂，hash碰撞需要复杂的处理逻辑范围查询，效率不高。kitty00000到kitty99999之间的所有K如果不能轻松扫描，只能逐一查询。
