Wednesday, August 24, 2016

Database Misc



http://www.raychase.net/2932
读模型
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,对于数据可靠性的问题,软件层面上冗余多份数据是唯一的办法。


Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts