数据存储漫谈

数据系统的核心就是两件事,读和写,当数据量还少的时候,读写的性能不会有明显区别,随着数据量的增大,读写变成了一个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)的时间。

原文发布于微信公众号 - 鸿的学习笔记(shujuxuexizhilu)

原文发表时间:2018-05-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我是攻城师

如何使用neo4j存储树形无限级菜单

4756
来自专栏Ceph对象存储方案

对象存储基础概念

对象存储诞生之初 谈到为什么要有对象存储,必须聊聊对象存储诞生之前的两大存储模型:块存储和文件存储。 块存储主要是将存储介质的空间整个映射给主机使用的,主机如果...

6134
来自专栏云飞学编程

Python爬虫的简单实现!用python爬虫自己做天气预报查询

最近小编在学习爬虫,就想找个东西练练手,小说、图片、音乐什么的都烂大街了,正好最近天气是越来越冷,小编窝家里自己敲了个天气简单查询的代码,请大家指正下!

1081
来自专栏java达人

Java 理论与实践: JDK 5.0 中更灵活、更具可伸缩性的锁定机制

多线程和并发性并不是什么新内容,但是Java 语言设计中的创新之一就是,它是第一个直接把跨平台线程模型和正规的内存模型集成到语言中的主流语言。核心类库包含一个T...

1986
来自专栏更流畅、简洁的软件开发方式

面向对象最重要的是“抽象”,三层最重要的也是“抽象”,没有抽象就不是真正的面向对象、三层。

  只用class的,那叫做“基于对象”,比如当初的vb6.0;只是分了三个项目,把以前写在一起的代码分成了三份,所谓的业务逻辑层就是一个传声筒,这一类自称三层...

2896
来自专栏木子昭的博客

Python3好用的原生api

对列表进行反序是一个很常见的操作, 但python反向切片的玩法实在是非常简洁, 让人无法拒绝, 其实对某一数据结构进行"反向"是一个很有意...

881
来自专栏牛客网

前端一面 - 阿里

13.算法题:电脑里有很多大小不一样的照片,我现在要复制到U盘上,但是U盘容量固定。让你写一个程序,挑选一组照片,让U盘的剩余空间最小。

1102
来自专栏服务端技术杂谈

百度、美团、58、阿里JAVA的面试题长啥样?

本文记录了我当年参加面试的时候面试官问我的问题,希望看到的人能有点收获。 百度 一面: 自我介绍 hashmap和hashtable区别 对线程安全的理解 讲讲...

3864
来自专栏向治洪

Java中的ReentrantLock和synchronized两种锁机制的对比

原文:http://www.ibm.com/developerworks/cn/java/j-jtp10264/index.html 多线程和并发性并不是什...

2335
来自专栏瓜大三哥

UVM

UVM模型 ? 《UVM实战》主要介绍UVM的使用。全书详尽介绍了UVM的factory机制、sequence机制、phase机制、objection机制及寄存...

2726

扫码关注云+社区

领取腾讯云代金券