读写模型整理笔记

标签: System Design 笔记 读写模型 | 发表时间:2015-04-27 01:45 | 作者:四火
分享到:
出处:http://www.raychase.net

读模型

1、主键读

最常见的读模型,说是主键,其实也包括其它索引键,或者联合主键。

常见实现:hash,时间复杂度可以接近O(1);B树或变种:时间复杂度接近O(log(n))。

关于B树和变种:

B树(B-树):本质上是二叉查找树的升级版,变成了平衡的N叉查找树,这个N的范围根据磁盘一次读取的块大小来调整,这样复杂度log n的底数就从2变成一个更大的数,减少了树的高度。除此以外,还有一些额外的优化,比如为了插入和删除的性能考虑,通常准备一些预留的空间,只要在当前块或者邻近块中找到空间写入,就避免了开销巨大的所有记录向后偏移的操作。

B树的阶:

  1. 一棵m阶的B树最多有m棵子树;
  2. 根节点至少有两棵子树;
  3. 每个非根分支节点至少有ceil(m/2)棵子树;
  4. 叶节点全部在同一层;
  5. 有x个孩子的非叶节点恰有x-1个递增排列的关键字。

读写模型整理笔记

图片来自 此页面

B+树:和B树相比,改变的地方包括:

  1. 全部关键字信息都放在叶子节点;
  2. 所有叶子节点串成一个linked list以便搜索;
  3. 存放重复的搜索键。

具体的区别可以参见 《Difference between B Tree and B+ Tree》,(下图出处)。

读写模型整理笔记 

B*树在B+树基础上做了进一步改进:

  1. 非叶子节点增加指向兄弟节点的指针(用以在节点满时,可以往兄弟节点放数据,减少节点创建的情况);
  2. 非叶子节点至少为2/3满的(关键字字数至少为最大值的2/3)。

2、指定页查询

指定页就意味着具备分页的概念,比如在DynamoDB的查询接口设计上,可以传入一个LastEvaluatedKey这样的对象,通过主键读的方式定位到本页读取的起始位置。但是,如果要随机指定页码号的查询,这种情况的复杂度在不同实现的情况下就有很大差异了,有的可以直接算出该页的位置,有的则需要从第一页开始一页页找下去。

常见实现:指定起始位置,条件查询的情况下返回数据子集。

3、范围查询

首先,数据可以根据某一属性排序,然后才存在范围查询的概念。比如用户的年龄在某个区间之内的查询。

常见实现:B树及其变种(这种情况下B+树比B树优越的地方就体现出来了,B+树可以直接扫描叶子节点的linked list即可)。

4、全数据扫描

这种访问模型通常意味着低速和高开销,一般多用作异步任务,比如报表系统,在低访问时段做定时的数据统计。通常非索引键查询本质上也是全数据扫描。

例子:数据库全表扫描,Hadoop上的数据集处理任务。

5、全文检索

常见实现:倒排索引。

6、前缀/后缀匹配

前缀匹配:Trie树;后缀匹配:后缀树。参见 《Trie树和其它数据结构的比较》

7、条件查询

常见实现:全表扫描;R树; Space-filling Curve

写模型

1、异步更新

先返回,不关注更新的事务性,更新操作在后台完成,这种方式具备最快的结果返回速度。

2、队列/双端队列

这种情况适用于吞吐量比较大并且非常不稳定的情形,借助队列的缓冲作用;也有一种是需要处理写入次序的问题,借助优先级队列的有序性。

3、批量写

很多情况下是异步的数据处理,比如数据回填、批量数据导出等等。

4、根据查询结果更新

就是把查询和更新这两步过程合并,使之具备原子性。比如Java中的compareAndSet操作,比如数据库的update语句跟上where子句等等。

5、插入或更新

upsert,如同hash map中的put,不管之前该记录是否存在,存在就覆盖,不存在就插入。

6、更新到多个replication

几乎所有的产品化的存储系统都会考虑replication,对于数据可靠性的问题,软件层面上冗余多份数据是唯一的办法。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

分享到:

相关 [模型 笔记] 推荐:

读写模型整理笔记

- - 四火的唠叨
最常见的读模型,说是主键,其实也包括其它索引键,或者联合主键. 常见实现:hash,时间复杂度可以接近O(1);B树或变种:时间复杂度接近O(log(n)). B树(B-树):本质上是二叉查找树的升级版,变成了平衡的N叉查找树,这个N的范围根据磁盘一次读取的块大小来调整,这样复杂度log n的底数就从2变成一个更大的数,减少了树的高度.

读书笔记:对线程模型的批评

- 阿贡 - 酷壳 - CoolShell.cn
——感谢Ian.Sian投递本文——. 多线程模型是主流的并发编程模型. 在过去几十年来,多线程模型一直是开发并发程序的有力工具. 1997年,NASA 的“火星探路者”号在执行任务的途中遭遇了严重的时序异常(参见 “What really happend on Mars“,注目 follow-up 中的现身说法),无法发回探测数据.

笔记

- 毛毛 - 游戏人生
我关于写代码的一些琐碎的看法. 之前没有把 Paul Graham 的 <黑客与画家> 一书读完, 上周就从同事那里把书带回家, 也一直没读, 到这周才有时间读完. 很久没有更新了 (一看时间, 整整 5 个月), 顺便把这篇写了几个月的感想放出来.. 这本书前面 8 章讲述的内容, 大多是我并不太感兴趣的, 比如财富, 比如创业.

Textmate笔记

- Sean Lee - Reborn
过去在Windows上还真的没有怎么太在意文本编辑器(也跟自己不是职业程序员有点关系吧. ),近来常在Mac上使用Textmate,真觉得一款好的文本编辑器实在非常必要. Textmate售价$58,很多人觉得贵,不过它真的不错. 为Finder加上“Open in textmate”按钮. 作者Henrik的主页上有详细的介绍.

OSX 笔记

- - C++博客-首页原创精华区
在vbox中安装10.7的方法:. 首先使用OS_X_Lion.iso.torrent下载操作系统的iso文件. 直接使用OS_X_Lion.iso安装,安装完之后使用HJMac.iso进行启动. 在win7 64bit上通过,但是在linux上没有通过. 升级,可以把10.7升级为10.7.4,方法是去苹果官方 http://support.apple.com/downloads 网站下载:.

模型制作

- 小鱼儿 - 非正常人类研究中心 – Mtime时光网
1.材料:一大袋的一次性筷子(花了60块钱);5支502胶水;5张粗砂纸;记号笔一只;锋利的美工刀片若干,破剪刀一把. 就是这种屌毛筷子,质量也太他妈的差了点,80%都是弯的 . 随便提一下:我的脚丫子还是蛮性感滴 . 开始动工了!!  先做门框跟房子的底架. 3.不好意思,忘了交代一下了,我是先画图纸的,看到那张纸了没有.

云笔记:跨平台笔记服务

- one dollar - 天涯海阁-Web2.0Share
云笔记是一款跨平台的笔记服务,目前提供了Android、iPhone、iPad客户端(FIT写字板、FIT Paper). 最早知道云笔记也是因为一直使用FIT写字板,发现FIT写字板更新之后支持了云同步,才发现了云笔记. 云笔记是新点科技旗下的产品,相信Mac用户都会知道FIT输入法,Mac和iOS上面很棒的输入法应用.

小岛笔记 Day1

- Qian - 吃素菜,彼此相爱。
去巴厘岛之前,我们对旅行进行了明确分工,我负责研究攻略. 我特意买了09年版的孤独星球,像小学生一样注了注,贴了几溜彩色便签. 临行前,我被各种词条式的信息膨胀着,能在10秒内,标出7座海神庙9座指示方位神庙的地图方位. 状态好时,能说出哪家餐馆在哪页地图的横几格竖几格. 包哥最怕坐飞机,又贵看着又不安全的事儿,有悖他的人生信条.

笔记本爱经

- Yuheng Kuang - 煎蛋
oioi:sein已经回家过年 :|. 名为KamaSutra(爱经)Lap,看看你与笔记本最亲近的姿势会是怎样 :) link. 老实说大部分时间,这玩意并没有让我感觉舒服. © oioi for 煎蛋 / 20回复 / 投稿 / 图片托管于又拍网. geek:极客2011日历(图集). 数码看新鲜:Dell 旋转屏幕笔记本.

shell 学习笔记

- tiger - 游戏人生
将脚本目录加到 PATH 中. 在 dash 中如何进行字符串替换. 将 rst 格式文档转换为 blog 可用的 html 代码. shell 脚本虽然不是非常复杂的程序, 但对于首次接触的我来讲, 多少还是有些忌惮. 不过, 接触任何新事物都需要勇敢面对, 逐步树立信心. 我是冲着把脚本写好去的, 所以, 我的目标是能够写出友好, 健壮, 优美的脚本..