Skip to content

四火的唠叨

一个纯正程序员的啰嗦

Menu
  • 所有文章
  • About Me
  • 关于四火
  • 旅行映像
  • 独立游戏
  • 资源链接
Menu

读写模型整理笔记

Posted on 04/27/201510/07/2024 by 四火

读模型

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

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

×Scan to share with WeChat

你可能也喜欢看:

  1. 数据挖掘学习笔记:分类、统计学习
  2. Java 容器类型复习笔记
  3. 写在在家办公四周之时
  4. 一些中文编程语言
  5. Groovy on Grails 交流活动

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

订阅·联系

四火,啰嗦的程序员一枚,现居西雅图

Amazon Google Groovy Hadoop Haskell Java JavaScript LeetCode Oracle Spark 互联网 亚马逊 前端 华为 历史 同步 团队 图解笔记 基础设施 工作 工作流 工具 工程师 应用系统 异步 微博 思考 技术 数据库 曼联 测试 生活 眼界 程序员 管理 系统设计 缓存 编程范型 美股 英语 西雅图 设计 问题 面向对象 面试

分类

  • Algorithm and Data Structure (30)
  • Concurrency and Asynchronization (6)
  • System Architecture and Design (43)
  • Distributed System (18)
  • Tools Frameworks and Libs (13)
  • Storage and Data Access (8)
  • Front-end Development (33)
  • Programming Languages and Paradigms (55)
  • Testing and Quality Assurance (4)
  • Network and Communication (6)
  • Authentication and Authorization (6)
  • Automation and Operation Excellence (13)
  • Machine Learning and Artificial Intelligence (6)
  • Product Design (7)
  • Hiring and Interviews (14)
  • Project and Team Management (14)
  • Engineering Culture (17)
  • Critical Thinking (25)
  • Career Growth (57)
  • Life Experience and Thoughts (45)

推荐文章

  • 谈谈分布式锁
  • 常见分布式系统设计图解(汇总)
  • 系统设计中的快速估算技巧
  • 从链表存在环的问题说起
  • 技术面试中,什么样的问题才是好问题?
  • 从物理时钟到逻辑时钟
  • 近期面试观摩的一些思考
  • RSA 背后的算法
  • 谈谈 Ops(汇总 + 最终篇):工具和实践
  • 不要让业务牵着鼻子走
  • 倔强的程序员
  • 谈谈微信的信息流
  • 评审的艺术——谈谈现实中的代码评审
  • Blog 安全问题小记
  • 求第 K 个数的问题
  • 一些前端框架的比较(下)——Ember.js 和 React
  • 一些前端框架的比较(上)——GWT、AngularJS 和 Backbone.js
  • 工作流系统的设计
  • Spark 的性能调优
  • “残酷” 的事实
  • 七年工作,几个故事
  • 从 Java 和 JavaScript 来学习 Haskell 和 Groovy(汇总)
  • 一道随机数题目的求解
  • 层次
  • Dynamo 的实现技术和去中心化
  • 也谈谈全栈工程师
  • 多重继承的演变
  • 编程范型:工具的选择
  • GWT 初体验
  • java.util.concurrent 并发包诸类概览
  • 从 DCL 的对象安全发布谈起
  • 不同团队的困惑
  • 不适合 Hadoop 解决的问题
  • 留心那些潜在的系统设计问题
  • 再谈大楼扔鸡蛋的问题
  • 几种华丽无比的开发方式
  • 我眼中的工程师文化
  • 观点的碰撞
  • 谈谈盗版软件问题
  • 对几个软件开发传统观点的质疑和反驳
  • MVC 框架的映射和解耦
  • 编程的未来
  • DAO 的演进
  • 致那些自嘲码农的苦逼程序员
  • Java 多线程发展简史
  • 珍爱生命,远离微博
  • 网站性能优化的三重境界
  • OSCache 框架源码解析
  • “ 你不适合做程序员”
  • 画圆画方的故事

近期评论

  • panshenlian.com on 初涉 ML Workflow 系统:Kubeflow Pipelines、Flyte 和 Metaflow
  • panzhixiang on 关于近期求职的近况和思考
  • Anonymous on 闲聊投资:亲自体验和护城河
  • 四火 on 关于近期求职的近况和思考
  • YC on 关于近期求职的近况和思考
  • mafulong on 常见分布式基础设施系统设计图解(四):分布式工作流系统
  • 四火 on 常见分布式基础设施系统设计图解(八):分布式键值存储系统
  • Anonymous on 我裸辞了
  • https://umlcn.com on 资源链接
  • Anonymous on 我裸辞了
© 2025 四火的唠叨 | Powered by Minimalist Blog WordPress Theme