首页 > 大数据平台 > 海量存储系列之二
2015
07-24

海量存储系列之二

在上一篇里面,我们对数据库的抽象的组成原理进行了简单的描述。在这一篇里面,我们一起来看看,如何能够使用kv这样的工具。来完成关系代数运算。
那么,让我们先来热热身:
海量存储系列之二 - 第1张  | 大话运维
这是一组数据,以pk作为主键,user_id和Name是外key.
那么,如果我要运行查询:Select * from tab where id = ?
应该如何进行呢?
这里需要一些额外的知识,在数据结构中,有那么一种结构,可以用于处理按照某个key找到value的过程,抽象来看,一种方法是二分查找法,一种方法是hash.
如果各位是java用户,那么二分查找的实现可以认为是个TreeMap的实现,而Hash的方法则可以认为是hashMap的实现。如果是个c/cpp的用户,那么就二分查找就对应map实现。而hash实现则对应stl里面的hash_map。
那么,这里的这个问题,我们就很容易可以解决了
以id作为map的key,以其他数据作为value,把所有数据都放入到map里面,然后再使用id=1作为key,从map中找到对应的value返回即可。(这一个部分,我们在后面的章节里面还会介绍,现在大家只需要有个大概的印象即可)
怎么样?是不是很简单?那么,我们来讨论更进一步的问题:
如果我想找到符合Select * from tab where user_id = 0的所有结果,应该如何去作?
仔细想想。那么第一种做法一定是这样。
把整个集合内的所有数据,都拿出来,然后找到user_id的数字,如果user_id=0,那么就认为是符合要求的记录,直接返回。
如果不是user_id=0,那么不匹配,丢弃这条记录即可。
这样一定可以找到所有符合要求的记录。
然而,这样作,带来的问题是,我有多少条记录,就需要进行多少次这样的匹配,那么,假设有100000000000000000条记录,就需要匹配这样多次,才能找到符合要求的记录。这是个悲剧。。
那么,怎么解决这个悲剧呢?
于是有些聪明人就又想起了map结构,hash或tree,不都可以按照k找到value么。那我们这里也可以利用这个map结构嘛。。
海量存储系列之二 - 第2张  | 大话运维
也就是说,以user_id作为key,id作为value,构建一个Map.不就又能进行快速查询了么。
于是,就有了数据库最重要的一个结构“索引” 这种以外键作为key,主键作为value的东西,有个专有的名字,叫做二级索引。
有了二级索引,我们的所有查询,都可以以接近O(LogN)(有序数据),或O(1)的效率找到我们需要的数据。是不是很爽?
但这不是银弹,你付出了空间成本,本质来说就是空间换时间的过程。同时,也会降低写入的效率。
怎么样?理解了没?如果自认为对这些都了解了,那么我们再来看一个问题:
海量存储系列之二 - 第3张  | 大话运维
如果我要找的是:Select …where user_id = ? And name = ‘袜子’
应该怎么做呢?
估计很多人都立刻又会想起那个Map,对的,但在这里,我想给出以下的几种查询的模式:
1. 遍历所有数据,取出一条以后,查看user_id = 0 and name=’袜子’是否符合要求,如果符合,则返回数据。
这是个合理的策略,空间最为节省,但带来的损耗是要遍历所有的数据。
2. 如果有个user_id -> pk的索引
海量存储系列之二 - 第4张  | 大话运维
,那么我们可以先按照user_id,找到一组符合要求的pk list.然后再根据pk list,再回到
海量存储系列之二 - 第5张  | 大话运维
取出符合要求的数据后,判断name=‘袜子’这个条件,如果符合,就返回,不符合,就丢弃。
这是个折衷策略,在空间和性能中,尽可能的找到个合理的区间的策略。
题外话,这个“根据pk list,再回到pk=>整个数据的kv表中,找出符合要求的数据后,判断name=‘袜子’这个条件,如果符合,就返回,不符合,就丢弃”的策略,在数据库有个专有名词,叫回表。
3. 组合索引
这是个新名词儿,但其实也是个很简单的概念。
直接上图:
海量存储系列之二 - 第6张  | 大话运维
海量存储系列之二 - 第7张  | 大话运维 ,其实就是个很简单的策略,先比较user_id进行排序,如果user_id相同,那么比较name排序。
这样,假定我们有100000条记录,属于100个用户,那么平均来看,每个用户就只有1000条记录了。
原来要回表1000条记录才能找到符合要求的数据,而如果使用组合索引,这1000条,也可以使用O(log2N)或者O(1)的策略进行检索啦。
在很多场景中,都能够提升效率和速度。但付出的是更多的存储空间。
好啦,这篇就介绍到这里,留个题目给大家:
海量存储系列之二 - 第8张  | 大话运维
假设有这么一组数据,性别有4种,user_id是一对多的关系,如果我想查询
select * from tab where user_id in (?,?,?,?) and 性别=’不明’
如何进行索引构建能够获得比较好的效果呢?
最后编辑:
作者:saunix
大型互联网公司linux系统运维攻城狮,专门担当消防员

留下一个回复