数据系统的核心就是两件事,读和写,当数据量还少的时候,读写的性能不会有明显区别,随着数据量的增大,读写变成了一个trade-off,当你拥有优秀的写性能时,读数据性能就会下降,反之亦然。下面的四个系统会用尽可能小的语言去概括核心,从读和写两个方面去评价它们。
注:这里不会详述具体工程遇到的问题,除了A系统外,其它的系统都有对应的实现。
假设有一条数据foo -> bar的键值对,将这个键值对写入一个文本,这个文本如下:
foo:bar
当有一条新的数据输入时,仅仅只是将新的数据添加再这条数据后面:
foo:bar
foo1:bar1
读取数据时,需要知道key值,去遍历找到对应的键值对,例如要找到foo1,便需要从头到尾匹配key值从而获得对应的value:bar1,如果有重复的数据,取最新的一条即可。这就是最简单的一个数据存储系统。
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表太占用内存,并且对范围查询不友好,调整下思路,在存储的时候,将数据进行有序排列,例如按照key值从大到小进行排序:
A_key:A_value
B_key:B_value
写入数据时,先写入内存中进行排序,之后将数据写入磁盘中。这时,只需要维护一张记录每个文件块的范围的表,查询数据时根据key值大小,从相应的数据块进行读取。
除了C系统,还有一种树结构,叫做B树。B树将数据分解为一个个固定大小的blocks或者是pages。每一个固定大小的块都有着自己的固定的位置,往往通过指针(ref)连接在一起。在查找数据时,会root开始查找数据,根据key值,不断沿着ref,找到对应的数据。如下:
网上搜的图 由于B树拥有着优秀的读性能,但是每一次写入数据都需要对树进行平衡。