读写模型整理笔记

读模型

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

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

6,661 次阅读

Leave a Reply

Your email address will not be published.

back to top