读写模型整理笔记

读模型

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-tree

图片来自 此页面

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

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

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

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,对于数据可靠性的问题,软件层面上冗余多份数据是唯一的办法。

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

4,783 次阅读

发表评论

电子邮件地址不会被公开。

back to top