索引

提到了索引,让我们再仔细看看索引。

1.Hash indexes

最简单的索引策略就是:将key值的offset存入在内存,使用hash表进行管理,在搜索时,会先根据key值找到offset,进而由offset找到对应的value值。不过看起来很简单,问题在于hash表需要保存在内存。一旦重启,索引就需要重新载入。

对于hash indexes,还有一个问题要解决,那就是如果存储的文件过大,超过了disk,那怎么办?一个很好的解决办法就是将log文件重新合并拆分成新文件(compaction)。在合并过程中,数据系统会将log上的老数据重新写入,只保留最新的数据,形成新的文件。这个合并过程,往往是在后台进行的,数据系统使用老文件依然可以对外提供读写服务。在合并完成后,数据系统就会切换到新文件上提供读写服务。在这个过程,我们也要重新组织hash表。

理论模型很简单,那么我们看看在实践中要怎么处理?

第一个要考虑的是文件格式,一般而言是选择二进制格式,其次是考虑你要如何删除数据,文件只能添加,那么要删除的key可以加上一个删除标志,表示这个key删除了,还有很重要的一点就是灾备恢复,如果服务器宕机了,存在内存里的hash表就会丢失,要再加载进内存的话,需要相当长的时间,所以一般数据库会考虑将hash表备份到磁盘里。再就是如果数据系统再写入log时,服务器突然宕机的话,写入到一半的文件可以考虑在恢复后直接删除。不过,这种数据库对于并发处理相当优秀,因为仅仅只是添加数据到文件末尾。

Hash表也存在问题,因为它对范围查询的支持很差,并且太过于依赖内存大小,但是它写的性能相当优秀,所以也是数据系统设计一个值得考虑的选项。

2.SSTable和LSM-Trees

SSTable的全称是sortedstring tables,它是在上面的append-only log的基础上做了改造,在每个文件分块根据key值有序的排列起来,而不单纯的只是添加在文件后面。这么做会获得很多好处,比如在合并(compaction)时有序的key相当方便,也不需要在内存里维护一个hash表,只要根据key值大小查找就好,同样的,范围查找和压缩性能也是相当的优秀。

那么我们如何创建和维护一个SSTable呢?首先当数据来临时,会先将数据写入内存里的某种树的数据结构(memtable),当memtable足够大时,会写入到磁盘上的文件,这时会很方便,因为这些数据已经在内存里排序好的了,再读取数据时,会先在memtable查找,再去磁盘文件搜索数据,与此同时,会在后台默默合并数据和删除不需要的数据。

为了防止memtable因为宕机丢失,我们可以单独写一个log到磁盘,这个log不在乎顺序,仅仅只是不断的添加到文件数据后面,为了数据恢复而存在的。性能优化的话,可能会使用布隆过滤器去加快查询速度

基于SSTable最出名的是LSM树。

3.B-Trees

除了基于log 的索引外,还有一种更出名的索引,那就是B-Trees。B树将数据分解为一个个固定大小的blocks或者是pages。每一个固定大小的块都有着自己的固定的位置,往往通过指针(ref)连接在一起。在查找数据时,会root开始查找数据,根据key值,不断沿着ref,找到对应的数据。

B树的子节点拥有的ref的个数称为负载因子,这个决定着存储空间和查询时的边界。如果需要更新数据时,只要在树结构上搜索数据,替换对应的page,而想要添加新的key时,只需要重新分配子节点就可以了。

B树的灾备恢复一般都是使用write-ahead日志()WAL,和SSTable所使用的日志一样,在写入之前会先将数据写入到WAL中。

当然在实践中不会如我说的这么简单,比如为了减少读取磁盘的次数,使用B+树等B树的变种。

原文发布于微信公众号 - 鸿的学习笔记(shujuxuexizhilu)

原文发表时间:2018-02-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏玄魂工作室

Hacker基础之Linux篇:基础Linux命令七

今天我们来了解一下几个Linux小命令,因为比较短的,而且不常用,所以会有三个(我就是这么任性) 1. paste paste命令用于合并文件的列 paste指...

3297
来自专栏Golang语言社区

棋牌游戏服务器架构: 详细设计(一) 内核设计

内核的几个组件被设计成Service,也就是说这几个模块都要实现如下接口: ? 图1 IService接口 Start方法用来启动服务。 ...

4945
来自专栏个人分享

Hbase基本操作~

每张表至少要有一个列簇,因此我们创建了info,现在,看看我们的表,执行下面list命令:

1042
来自专栏漫漫全栈路

Nginx配置文件nginx.conf详解

最近折腾Ubuntu比较多,也基本原理了Windows和IIS了,论一个软狗的堕落史。既然换到Ubuntu系统上来,勉强算个web开发人员的我当然用的最多的就...

5967
来自专栏Spark学习技巧

高性能:MYSQL异步客户端

实时处理领域,当需要使用外部存储数据染色的时候,需要慎重对待,不能让与外部系统之间的交互延迟对流的整个进度取决定性的影响。

3262
来自专栏wireboy编程加油站

用Vue.js搭建一个小说阅读网站

这是一个使用vue.js + mint-ui + .net core api的小说网站。

2610
来自专栏遊俠扎彪

如何解决MySQL中文乱码及插入中文信息错误的问题

从前和最近,帮人做点东西的时候,都遇到过MySQL与中文不兼容的问题,从前都是凭借尝试与运气解决问题这次好好总结一下:

1996
来自专栏偏前端工程师的驿站

网页优化系列一:合并文件请求(asp.net版)

  最近因公司需要对网站的优化处理学习了一番,现在借本系列博文与大家分享一下自己的学习成果,有纰漏处请大家多多指正。   首先推荐一篇十分全面的网页优化文章  ...

2138
来自专栏Golang语言社区

棋牌游戏服务器架构: 详细设计(一) 内核设计

内核的几个组件被设计成Service,也就是说这几个模块都要实现如下接口: ? 图1 IService接口 Start方法用来启动服务。 ...

35910
来自专栏晨星先生的自留地

攻破VulnOS(3)之挑战PwnLad

4266

扫码关注云+社区

领取腾讯云代金券