海量存储系列之七

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

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树的核心是几个关键词

数组:每一个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的基础上。增加两条新的规则

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

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

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

本文来源于"阿里中间件团队播客",原文发表时间"  2011-12-22"

「数据密集型系统搭建」原理篇｜用什么方式存储数据最合适 本篇来聊聊数据存储的内容，看看程序世界里数据是以什么形式存在的？为了描述数据并把它们和这个现实世界关联起来我们一般都是如何去进行表达的？最后通过我们习惯的表达方式再结合数据结构是如何存储下来的？   
「数据密集型系统搭建」原理篇｜数据类型不怕精挑细选 本篇围绕MySQL数据库的底层存储模型、列类型来聊聊数据库表设计及建模中要注意的事项，剖析最根源的底层物理存储文件，用最真实的数据剖析来证明和解答开发过程中的疑惑。
《如何使用Tair增强数据结构构建丰富在线实时场景》电子版地址 阿里云内存数据库Tair在完全兼容Redis的基础上，推出了 Tair 增强数据结构。Tair的增强数据结构有什么独特的优势？如何使用 TairRoaring 构建企业级实时人群服务？如何使用TairSearch 构建在线交互搜索？我们一一揭晓。
图文存储常识：单机、集中、分布式、云、云原生存储 本文主要对杨传辉（日照）《大规模分布式存储系统原理解析与架构实战》、大话存储、网络资源(具体参考文末链接)及个人理解进行整理，意在构建出存储发展基本轨迹和一些基本常识，让更多像我一样的初入者有个宏观上的认知。 存储发展史 从单机到互联网，存储作为的基础设施，主要发展都是围绕构建 低成本、高性能、可扩展、易用的目标进行演进，时至今日，在形态上存储分为单机存储、集中存储、分