数据存储漫谈

数据系统的核心就是两件事，读和写，当数据量还少的时候，读写的性能不会有明显区别，随着数据量的增大，读写变成了一个trade-off，当你拥有优秀的写性能时，读数据性能就会下降，反之亦然。下面的四个系统会用尽可能小的语言去概括核心，从读和写两个方面去评价它们。

注：这里不会详述具体工程遇到的问题，除了A系统外，其它的系统都有对应的实现。

最简单的数据系统A

假设有一条数据foo -> bar的键值对，将这个键值对写入一个文本，这个文本如下:

foo:bar

当有一条新的数据输入时，仅仅只是将新的数据添加再这条数据后面:

foo:bar
foo1:bar1

读取数据时，需要知道key值，去遍历找到对应的键值对，例如要找到foo1，便需要从头到尾匹配key值从而获得对应的value:bar1，如果有重复的数据，取最新的一条即可。这就是最简单的一个数据存储系统。

• 写：这个数据系统写的性能相当优秀，因为它没有做任何操作，仅仅只是把新来的数据添加到文件的末尾，这意味着数据系统可以并发的去写数据，而不需要担心任何冲突。
• 读: 获得了极佳的写性能后，读数据的能力相当差，为了找一个数据，它平均需要花费O(n)的时间，随着数据的增多，读性能下降的会更加严重。

进阶版数据系统B

A系统获得了优秀的写性能，但却有着相当糟糕的读性能，为了提高读性能，需要做进一步改进，增加一个索引。最简单的索引就是Hash索引。Hash表的原理不详述了，具体可以参考:hash表。数据系统A已经存储了如下数据：

foo:bar
foo1:bar1

为了更快的读取数据，可以在内存里维护一张hash表，把每个key值出现的位置记录下来，当需要读取数据时，直接从hash表中读取:

foo:0 foo1:8

也就是当B系统需要读取foo1时，会先去hash表找到foo1，找到对应的位移8，回到存储数据的文件直接将指针定位到8这个位置，即可获得value，而不需要遍历整个数据文件。

• 写：在系统B，牺牲了一部分写的性能，因为每次写入数据时，需要更新hash表，再写入数据，总的来说，写的性能依然优秀
• 读：在内存中建立一张hash表后，每次读取数据都不需要遍历文本文件了，只需要去hash表找到对应的key值，相对于遍历数据文件，读的性能获得了大大提高，但是对于范围查询依然不够友好。

主流数据系统C

B系统的读性能获得了极大的提升，但是hash表太占用内存，并且对范围查询不友好，调整下思路，在存储的时候，将数据进行有序排列，例如按照key值从大到小进行排序：

A_key:A_value
B_key:B_value

写入数据时，先写入内存中进行排序，之后将数据写入磁盘中。这时，只需要维护一张记录每个文件块的范围的表，查询数据时根据key值大小，从相应的数据块进行读取。

• 写：C系统的写性能相对于B有所下降，但是总体而言依旧优秀，花费的仅仅是在内存里进行排序的时间。
• 读：读的性能相对于B提高了，hash表占据内存的空间小了，由于记录了数据的大小，通过二分搜索的方式小量增加了单个key值读取的性能外，获得范围查询的读性能的提升。

主流数据系统D

除了C系统，还有一种树结构，叫做B树。B树将数据分解为一个个固定大小的blocks或者是pages。每一个固定大小的块都有着自己的固定的位置，往往通过指针(ref)连接在一起。在查找数据时，会root开始查找数据，根据key值，不断沿着ref，找到对应的数据。如下：

网上搜的图 由于B树拥有着优秀的读性能，但是每一次写入数据都需要对树进行平衡。

• 写：写的性能大幅下降，因为每一次写入数据都需要对树进行平衡
• 读：获得了极佳的读取性能，理论上每一次的搜索都是O(log)的时间。