文档章节

索引:如何在海量数据中快速查找某个数据?

o
 osc_g8254g7s
发布于 2019/08/19 22:35
字数 2321
阅读 33
收藏 0

精选30+云产品,助力企业轻松上云!>>>

转自:https://blog.csdn.net/every__day/article/details/90763607

《数据结构与算法之美》

前面讲过MySQL数据库索引实现原理,底层是依赖B+树这种数据结构来实现的。那类似Redisp 这要的Key-Value数据库中的索引,又是怎么实现的呢?底层依赖的又是什么数据结构呢?

为什么需要索引?
在实际的软件开发中,业务纷繁复杂,功能千变万化,但是,万变不离其宗。如果抛开业务和功能的外壳,其实它们的本质都可以抽象为“对数据的存储和计算”。对应到数据结构和算法中,那“存储”需要的就是数据结构,“计算”需要的就是算法。

对于存储的需求,功能上无外乎增删改查。这其实并不复杂。但是,一旦存储的数据多了,那性能就成了这些系统要关注的重点,特别是在一些跟存储相关的基础系统(比如MySQL数据库、分布式文件系统等)、中间件(比如消息中间件RocketMQ等)中。

“如何节省存储空间、如何提高数据增删改查的执行效率”,这个问题就成了设计的重点。而这些系统的实现,都离不开一个东西,那就是索引。不夸张的说,索引设计的好坏,直接决定了这些系统是否优秀。

索引这个概念,非常好理解。你可以类比书籍的目录来理解。如果没有目录,我们想要查找某个知识点的时候,就要一页一页的翻。通过目录,我们就可以快速定位相关的知识点的页数,查找的速度也会有质的提高。

索引的需求定义
索引的概念不难理解,在设计索引的过程中,需要考虑一些因素,换名话说,我们该如何定义清楚需求呢?

对于系统设计需求,我们一般可以从功能性需求和非功能性需求两方面来分析。

1. 功能性需求

对于功能性需求大致要考虑以下几点。

数据是格式化的还是非格式化数据?要构建索引的原始数据,类型很多。我把它分为两类,一类是结构化数据,比如MySQL中的数据;另一类是非结构化数据,比如搜索引擎中的网页。对于非结构化数据,我们一般需要做预处理,提取出查询关键词,对关键词构建索引。

数据是静态数据还是动态数据?如果原始是一组静态数据,也就是说,不会有数据的增加、删除、更新操作,所以,我们在构建索引的时候,只需要考虑查询效率就可以了。这样,索引的构建就相对简单些。不过,大部分情况下,我们都是对动态数据构建索引,也就是说,我们不仅要考虑到索引的查询效率,在原始数据更新时,我们还需要动态的更新索引。支持动态数据集合的索引,设计越来相对更复杂些。

索引是存储在内存还是硬盘?如果索引存储在内存中,那技术要求的速度肯定要比存储的磁盘中的高。但是,如果原始数据量很大的情况下,对应的索引可能也会很大。这个时候,因为内存有限,我们可能就不得不将索引存储在硬盘中了。实际上,还有第三种情况,那就是一部分存储在内存,一部分存储在磁盘,这样就可以兼顾内存消耗和查询效率。

单值查找还是区间查找?所谓单值查找,也就是根据查询关键词等于某个值的数据。这种查询需求最常见。所谓区间查找,就是查找关键词处于某个区间值的所有数据。实际上,不同的应用场景,查询的需求会多种多样。

单关键词查找还是多关键词组合查找?比如,搜索引擎中构建的索引,既要支持一个关键词的查找,比如“数据结构”,也要支持组合关键词查找,比如“数据结构 AND算法”。对于单关键词查找,索引构建起来相对简单些。对于多关键词查找来说,要分多种情况。像MySQL这种结构化数据的查询需求,我们可以实现针对多个关键词组合,建立索引;对于像搜索引擎这样的非结构数据的查询需求,我们可以针对间个关键词构建索引,然后通过集合操作,比如求并集、求交集等,计算出多个关键词组合的查询结果。

实际上,不同的场景,不同的原始数据,对于索引的需求也会千差万别。

2.非功能性需求

不管是存储在内存中还是磁盘中,索引对存储空间的消耗不能过大。如果存储在内存中,索引对占用存储空间的限制就会非常苛刻。毕竟内存空间非常有限,一个中间件启动后就占用几个GB的内存,开发者显然是无法接受的。如果存储在硬盘中,那索引对占用存储空间的限制,稍微会放宽一些。但是,我们也不能掉以轻心。因为,有时候,索引对存储空间消耗会超过数据。

在考虑索引查询效率的同时,我们还是考虑索引的维护成本。索引的目的是提高查询效率,但是,基于动态数据集合构建的索引,我们还要考虑到索引的维护成本。因为在原始数据动态增删改的同时,我们也需要动态的更新索引。而索引的更新势必会影响到增删改的操作性能。

构建索引常用的数据结构有哪些?
实际上,常用来构建索引的数据结构,就是我们之前讲过的几种支持动态数据集合的数据结构。比如,散列表、红黑树、跳表、B+树。除此之外,位图、布隆过滤器可以作为辅助索引,有序数组可以用来对静态数据构建索引。

我们知道,散列表增删改查操作的性能非常好,时间复杂度是O(1)。一些键值数据库,比如Redis、Memcache,就是使用散列表来构建索引的。这类索引,一般都构建在内存中。

红黑树作为一种常用的平衡二叉查找树,数据插入、删除、查找的时间复杂度是O(logn),也非常适合用来构建内存索引。Ext文件系统中,对磁盘块的索引,用的就是红黑树。

B+ 树比起红黑树来说,更加适合构建存储在磁盘的索引。B+树是一个多叉树,所以,以相同个数的数据构建索引,B+树的高度要低于红黑树。当借助索引查询数据的时候,读取B+树索引,需要的磁盘IO次数更少。所以,大部分关系型数据库的索引,比如MySQL、Oracle,都是用B+树来实现的。

跳表也支持快速添加、删除、查找数据。而且,我们通过灵活调整索引结点个数和数据个数之间的比例,可以很好的平衡对内存的消耗及其查询效率。Redis中的有序集合,就是用跳表来构建的。

除了散列表、红黑树、B+树、跳表之外,位图和布隆过滤器这两个数据结构,也可以用于索引中,辅助存储在磁盘中的索引,加速数据查询的效率。我们来看下,具体是怎么做的?

布隆过滤器有一定的判错率。但是,我们可以规避它的短处,发挥它的长处。尽管对于判定存在的数据,有可能并不存在,但是对于判定不存在的数据,那肯定就不存在。而且,布隆过滤器还有一个更大的特点,那就是内存占用非常少。我们可以针对数据,构建一个布隆过滤器,并且存储在内存中。当要查询数据的时候,我们可以先通过布隆过滤器,判定是否存在。如果数据不存在,那我们就没必要读取磁盘中的索引了。对于数据不存在的情况,数据查询就更加快速了。

实际上,有序数组也可以被作为索引。如果数据是静态的,也就是不会插入、删除、更新操作,那我们可以把数据的关键词(查询用的)抽取出来,组织成有序数组,然后利用二分查找算法来快速查找数据。

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Java线程池

前言 Java中对线程池的抽象是ThreadPoolExecutor类,Executors是一个工具类,内置了多种创建线程池的方法: newFixedThreadPool:固定长度线程池 newCachedThreadPool :可缓存线程池 newSin...

nullpointerxyz
26分钟前
35
0
Python笔记:用Python制作二维码

这些年,二维码在我国的日常使用频率特别大。因为其具有简单及安全性吧!除了用网络工具制作二维码,其实用JavaScript或Python也可以制作二维码,而且更有个性。 示例一(制作普通黑白二维码...

tengyulong
38分钟前
0
0
Redis-初体验/数据结构

定义: Redis 是 C 语言开发的一个开源的(遵从 BSD 协议)高性能键值对(key-value)的内存数据库,可以用作数据库、缓存、消息中间件等。它是一种 NoSQL(not-only sql,泛指非关系型数据库...

心田已荒
41分钟前
15
0
如何在保留订单的同时从列表中删除重复项? - How do you remove duplicates from a list whilst preserving order?

问题: Is there a built-in that removes duplicates from list in Python, whilst preserving order? 是否有内置的程序在保留顺序的同时从Python列表中删除重复项? I know that I can us...

fyin1314
今天
29
0
以太坊智能合约开发常见的10个安全问题

本文介绍CheckMarx安全研究小组通过扫描公开的以太坊智能合约所发现的Solidity智能合约开发中常见的十大安全问题,其中__未检查的外部调用__ 和 高成本循环 分列排行榜前两名。该安全问题排行...

区块链教程
今天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部