若谷学院
互联网公司技术架构分享

海量存储系列之二

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

在上一篇里面,我们对数据库的抽象的组成原理进行了简单的描述。在这一篇里面,我们一起来看看,如何能够使用kv这样的工具。来完成关系代数运算。

那么,让我们先来热热身:

这是一组数据,以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结构嘛。。

也就是说,以user_id作为key,id作为value,构建一个Map.不就又能进行快速查询了么。

于是,就有了数据库最重要的一个结构“索引” 这种以外键作为key,主键作为value的东西,有个专有的名字,叫做二级索引。

有了二级索引,我们的所有查询,都可以以接近O(LogN)(有序数据),或O(1)的效率找到我们需要的数据。是不是很爽?

但这不是银弹,你付出了空间成本,本质来说就是空间换时间的过程。同时,也会降低写入的效率。

怎么样?理解了没?如果自认为对这些都了解了,那么我们再来看一个问题:

如果我要找的是:Select …where user_id = ? And name = ‘袜子’

应该怎么做呢?

估计很多人都立刻又会想起那个Map,对的,但在这里,我想给出以下的几种查询的模式:

1. 遍历所有数据,取出一条以后,查看user_id = 0 and name=’袜子’是否符合要求,如果符合,则返回数据。

这是个合理的策略,空间最为节省,但带来的损耗是要遍历所有的数据。

2. 如果有个user_id -> pk的索引

,那么我们可以先按照user_id,找到一组符合要求的pk list.然后再根据pk list,再回到

取出符合要求的数据后,判断name=‘袜子’这个条件,如果符合,就返回,不符合,就丢弃。

这是个折衷策略,在空间和性能中,尽可能的找到个合理的区间的策略。

题外话,这个“根据pk list,再回到pk=>整个数据的kv表中,找出符合要求的数据后,判断name=‘袜子’这个条件,如果符合,就返回,不符合,就丢弃”的策略,在数据库有个专有名词,叫回表。

3. 组合索引

这是个新名词儿,但其实也是个很简单的概念。

直接上图:

:-),其实就是个很简单的策略,先比较user_id进行排序,如果user_id相同,那么比较name排序。

这样,假定我们有100000条记录,属于100个用户,那么平均来看,每个用户就只有1000条记录了。

原来要回表1000条记录才能找到符合要求的数据,而如果使用组合索引,这1000条,也可以使用O(log2N)或者O(1)的策略进行检索啦。

在很多场景中,都能够提升效率和速度。但付出的是更多的存储空间。

好啦,这篇就介绍到这里,留个题目给大家:

假设有这么一组数据,性别有4种,user_id是一对多的关系,如果我想查询

select * from tab where user_id in (?,?,?,?) and 性别=’不明’

如何进行索引构建能够获得比较好的效果呢?

http://rdc.taobao.com/team/jm/archives/1362 下一篇

原文出自:

好烂呀没啥价值凑合看看还不错很精彩 (还没有人评分)
Loading...
本站文章来自互联网一线技术博客,若有侵权,请联系我们:若谷技术学院 » 海量存储系列之二
关注若谷技术,获得个性化即时架构文章推送

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

全球互联网技术架构,前沿架构参考

联系我们博客/网站内容提交