海量存储系列之七

http://rdc.taobao.com/team/jm/archives/1379  上一篇

在上一个章节，我们阐述了分布式场景下，事务的问题和一些可能的处理方式后，我们来到了下一章节

Key-value存储

这一章，我们将进入k-v场景，其实，在大部分场景下，如果某个产品宣称自己的写读tps超过其他存储n倍，一般来说都是从k-v这个角度入手进行优化的，主要入手的点是树的数据结构优化和锁的细化，一般都能在一些特定的场景获得5-10倍的性能提升。由此可见key-value存储对于整个数据存储模型是多么的重要。

好吧，那么我们来进入这个章节，用最简单和浅显的话语，阐述这些看起来很高深的理论吧 : )

在未来的几篇中，我们将大概的介绍和分析如下几种比较有特点的数据结构，并探讨其优势劣势以及适用的场景。

让我们先从映射入手吧，所谓映射，就是按照key找到value的过程，这个过程几乎就是我们处理数据的最核心数据结构了。

如何能够根据一个key找到对应的value呢？

一类是hash map.最简单的实现就是算一个key数据的hashCode.然后按照桶的大小取mod.塞到其中的一个桶里面去。如果出现冲突怎么办呢？append到这个桶内链表的尾部就行了。

还有一类呢，我们可以抽象的认为是一个有序结构。之所以把它归类到有序结构原因也很简单，因为只有有序才能做二分查找。。。举些有序结构的例子吧： 1. 数组 2. 各类平衡二叉树 3. B-树类族 4. 链表

这些数据结构如果想进行快速查找，都需要先让他们有序。然后再去做log2N的二分查找找到对应的key。

从原教旨上来说，这就是我们要用的key-value的主要结构了。

那么，hash和有序结构，他们之间有什么样的差别呢？我们来进行一下简单的比较

基本上来说，核心区别就是上面的这点，hash单次查询效率较高，但为了保证O(1)效率，对空间也有一定要求。而有序结构，查询效率基本是O(log2N)这个级别。但有序结构可以支持范围查找，而hash则很难支持。

所以，一般来说我们主要在使用的是有序结构来进行索引构建，因为经常需要查询范围。

不过，所有数据库几乎都支持hash索引，如果你的查询基本都是单值的，那么可以找一找稳定的hash索引，他们能从一定程度上提升查询的效率。

在这里，我们主要讨论有序结构，对于数据库或nosql来说，有序结构主要就是指b-tree或b-tree变种。那么我们先来介绍一下什么叫b-tree作为讨论磁盘结构的入门吧。

先上图(copy的，这是个b+tree。版权方请找我)

首先进行词汇科普：b-tree只有两类，一类叫b-tree，就是btree，还有一类是b+tree，但b-tree不是b”减”树的意思。这个大家不要再跟当年的我犯同样的错误哟 :__0

那么b树的核心是几个关键词

1.      树高:一般来说，树的高度比较低。三到五层

2.      数组:每一个node，都是一个“数组”，数组是很关键的决定性因素，我们后面写入和读取分析的时候会讲到。

没了呵呵

然后我们进行一下读取和写入的模拟。

读取来说：如果我要查找28这个数据对应的value是多少，路径大概是：首先走root节点，取出root node后，对该数组进行二分查找，发现35>28>17,所以进入branch节点中的第二个节点，取出该节点后再进行二分查找。发现30>28>26，所以进入branch节点的p2 value，取出该节点，对该三个值的数组进行二分查找，从而定位到28这个数据的对应value。

而写入删除则涉及到分裂和合并这两个btree最重要的操作，比如，要写入37，那么会先找到36所应该被插入的数组[36,60]这个数组，然后判断其是否有空，如果有空，则对该数组进行重新排序。而如果没有空，则必须要进行分裂。分裂的缘由是因为组成b-tree的每一个node,都是一个数组，数组最大的特性是，数组内元素个数是固定的。因此必须要把原有已经满掉的数组里面的一半的数据拿出来，放到新的一个新建立的空数组中，然后把要写入的数据写入到老或新的这两个数组里面的一个里面去。

【这里要留个问题给大家了，我想问一下，为什么b-tree要使用数组来存储数据呢？为什么不选择链表等结构呢？】

对于上面的这个小的b-tree sample里面呢，因为数组[35,60]，数组已经满了，所以要进行分裂。于是数组在插入了新值以后，变成了两个[35,36] 和[60] ，然后再改变父节点的指针并依次传导上去即可。

当出现删除的时候，会可能需要进行合并的工作，也就是写入这个操作的反向过程。在一些场景中，因为不断地插入新的id,删除老的id，会造成b-tree的右倾，这时候需要有后台进程对这种倾向进行不断地调整。

基本上，这就是b-tree的运转过程了。

B+tree

B+tree 其实就是在原有b-tree的基础上。增加两条新的规则

1.      Branch节点不能直接查到数据后返回，所有数据必须读穿或写穿到leaf节点后才能返回成功

2.      子叶节点的最后一个元素是到下一个leaf节点的指针。

这样做的原因是，更方便做范围查询，在b+树种，如果要查询20~56.只需要找到20这个起始节点，然后顺序遍历，不再需要不断重复的访问branch和root节点了。

发现每一种数据结构都需要去进行简介才能够比较方便的了解到他们的特性，所以在后续的章节还会介绍几种有代表性的树的结构都会针对性的加以介绍。