http://www.raychase.net/2932
读模型
1、主键读
最常见的读模型，说是主键，其实也包括其它索引键，或者联合主键。
常见实现：hash，时间复杂度可以接近O(1)；B树或变种：时间复杂度接近O(log(n))。
关于B树和变种：
B树（B-树）：本质上是二叉查找树的升级版，变成了平衡的N叉查找树，这个N的范围根据磁盘一次读取的块大小来调整，这样复杂度log n的底数就从2变成一个更大的数，减少了树的高度。除此以外，还有一些额外的优化，比如为了插入和删除的性能考虑，通常准备一些预留的空间，只要在当前块或者邻近块中找到空间写入，就避免了开销巨大的所有记录向后偏移的操作。
B树的阶：
- 一棵m阶的B树最多有m棵子树；
- 根节点至少有两棵子树；
- 每个非根分支节点至少有ceil(m/2)棵子树；
- 叶节点全部在同一层；
- 有x个孩子的非叶节点恰有x-1个递增排列的关键字。
图片来自此页面。
B+树：和B树相比，改变的地方包括：
- 全部关键字信息都放在叶子节点；
- 所有叶子节点串成一个linked list以便搜索；
- 存放重复的搜索键。
具体的区别可以参见《Difference between B Tree and B+ Tree》，（下图出处）。
B*树在B+树基础上做了进一步改进：
- 非叶子节点增加指向兄弟节点的指针（用以在节点满时，可以往兄弟节点放数据，减少节点创建的情况）；
- 非叶子节点至少为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，对于数据可靠性的问题，软件层面上冗余多份数据是唯一的办法。
