数据结构与算法笔记:高级篇 - 索引:如何在海量数据中快速查找某个数据?

概述

在 B+ 树章节,我们讲了 MySQL 数据库索引的实现原理。MySQL 底层依赖 B+ 树这种数据结构。那类似 Redis 这样的 Key-Value 数据库中的索引是怎么实现的呢?底层依赖的又是什么数据结构?

本章,我们就来讲一下索引这种常用的计数解决思路,底层往往会依赖哪些数据结构。同时,通过索引这个应用场景,我也带你回顾一下,之前我们学过的几种支持动态集合的数据结构。


为什么需要索引?

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

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

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

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

索引的需求定义

索引的概念不难理解,我想你应该已经搞明白。接下来,我们就分析一下,在设计索引的过程中,需要考虑到的一些因素,换句话说,我们该如何定义清楚需求呢?

对于系统设计需求,我们一般可以从功能性需求非功能性需求两方面来分析。因此,这个问题也不例外。

1.功能性需求

对于功能性需求需要考虑的点,大致可以概括成下面这几点。

数据是格式化数据还是非格式化数据? 要构建索引的原始数据,类型有很多。我把它们分为两类:

  • 一类是格式化数据,比如 MySQL 中的数据;
  • 另一类是非结构化数据,比如搜索引擎中的网页。对于非结构化数据,我们一般需要做预处理,提取出查询关键词,对关键词构建索引。

数据是静态数据还是动态数据?

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

索引存储在内存还是磁盘?

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

单值查找还是区间查找?

  • 所谓单值查找,也就是查询关键词等于某个值的数据,这种查询需求最常见。
  • 所谓区间查找,就是查找关键词处于某个区间值的所有数据。

你可以类比 MySQL 数据库的查询需求,自己想象一下。实际上不同的应用场景,查询的需求会多种多样。

单关键词查找还是多关键词查找? 比如,搜索索引中构建的索引,既要支持一个关键词的查找(比如 “数据结构”),也要支持组合关键词查找(比如 “数据结构 AND 算法”)。

  • 对于但关键词的查找,索引构建起来相对简单些。
  • 对于多关键词查询来说,要分多钟情况。
    • 向 MySQL 这种结构化数据的查询需求,我们可以针对多个关键词的组合,建立索引;
    • 对于像搜索引擎这样的非结构数据的查询需求,我们可以针对单个关键词构建索引,然后通过集合操作,求并集、求交集,计算出多个关键词组合的查询结果。

实际上,不同的场景,不同的原始数据,对于索引的需求也会千差万别。这里只是列举了一些比较有共性的需求。

2.非功能性需求

讲完了功能性需求,再来看下,索引设计的非功能性需求。

不管是存储在内存中还是磁盘中,索引对存储空间的消耗不能过大

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

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

构建索引常用的数据结构有哪些?

刚刚从很宏观的监督,总结了在索引设计的过程中,需要考虑的一些共性因素。现在,我们就来看下,对于不同需求的索引结构,底层一般是使用哪种数据结构的。

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

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

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

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

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

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

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

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

总结

本章是一个总结课。从索引这个非常常用的技术方案,给你展示了散列表、红黑树、跳表、B+ 树、位图、布隆过滤器、有序数组这些数据结构的应用场景。学习完这篇文章后,不知道你对数据结构以及索引,有没有更加清晰的认识呢?

从本章的内容中,你应该可以看出,架构设计离不开数据结构和算法。要向成长为一名优秀的架构师、基础架构师,数据结构和算法的根基一定要打稳。因为,哪些看似很惊艳的架构设计思路,实际上,都是来自最常用的数据结构和算法。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/753356.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用青否数字人直播软件有哪些优势?

使用青否数字人主播主要具有以下优势: 1、降低直播门槛 在垂直程度较高、专业度更强的行业,面对相关品牌们“专业主播难培养”的问题。数字人主播的学习技能和灵活优势尽显。通过数字人直播可以借助知识库配置与AI能力,快速获得技术性知识&am…

【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 螺旋矩阵填数(100分) - 三语言AC题解(Python/Java/Cpp)

🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 &#x1f…

c语言--指针

前言 欢迎来到我的博客 个人主页:北岭敲键盘的荒漠猫-CSDN博客 本文整理c语言中指针的相关知识点。 指针概念 指针存储的就是数据的地址。 直观理解: 李华家是北洋路130号1单元101 用变量处理数据: 我们去李华家拿数据。 用指针处理数据: 我们去北洋路130号1单元101拿数据…

石墨舟氮气柜的特点和使用要求介绍

石墨舟是一种在半导体、太阳能光伏等高科技产业中广泛使用的专用工具,主要由高纯度石墨材料制成。它的形状通常像一只船,因此得名“石墨舟”。石墨舟主要用于承载硅片或其他基板材料通过各种高温处理过程,是制造半导体器件和太阳能电池片的关…

二叉树的方法

目录 一、二叉树的定义 ​编辑 二、二叉树的创建 三、二叉树的遍历 1、前序遍历 2、中序遍历 3、后序遍历 4、层序遍历 四、二叉树遍历方法的使用 五、二叉树的操作 1、节点的个数 2、叶子节点的个数 3、第k层节点的个数 4、二叉树的高度 5、检查值为value的元素…

「2024抢先看」6款免费的ai变声器,助你开麦就变声

你是否也曾想模仿电视剧中的明星说话,或者想像泰勒一样有着独特的嗓音呢?通过免费版ai变声器,你可以轻松实现实时变声,将你的声音转换为专业且动听的声音,让身边的朋友对你刮目相看。在本文中,小编将分享20…

服务器日志事件ID4107:从自动更新 cab 中提取第三方的根目录列表失败,错误为: 已处理证书链,但是在不受信任提供程序信任的根证书中终止。

在查看Windows系统日志时,你是否有遇到过事件ID4107错误,来源CAPI2,详细信息在 http://www.download.windowsupdate.com/msdownload/update/v3/static/trustedr/en/authrootstl.cab 从自动更新 cab 中提取第三方的根目录列表失败,…

简单的本地局域网的前后端接口联调

由于项目被赶进度了,急于前后端联调接口,但是我又没钱买服务器(主要我也不会部署),所以我这里就紧急找一个后端的大神朋友请教了一下:苏泽SuZe-CSDN博客 提示:这里不讲后端怎么写接口、前端怎么…

C#——里氏转换详情

里氏转换 里氏转换就是派生类的对象赋值给父类对象,反之则不行 实例 : 先创键一个类然后继承 调用

双路视频同屏显示(拼接)-基于野火Zynq7020开发板

前情提要 米联客FDMA驱动OV5640摄像头—基于野火Zynq7020开发板 本文在此基础上,实现了双路视频拼接。将ov5640输出的1024600的图像数据缩放为512600,分两路写入ddr3,并且显示在1024*600的RGB屏幕中。 纯FPGA也可以按此方法实现。 总体BLOC…

【C++ 初阶路】--- 类和对象(末)

目录 一、const成员1.1 取地址及const取地址操作符重载 二、再谈构造函数2.1 构造函数体赋值2.2 初始化列表2.3 explicit关键字 三、static成员3.1 概念3.2 特性 四、友元4.1 友元函数4.2 友元类 五、内部类六、匿名对象 一、const成员 将const修饰的“成员函数”称之为const成…

Qt creator实现一个简单计算器

目录 1 界面设计 2 思路简介 3 代码 目录 1 界面设计 ​2 思路简介 3 代码 3.1 widget.h 3.2 widget.c 4 完整代码 在这里主要记载了如何使用Qt creator完成一个计算器的功能。该计算器可以实现正常的加减乘除以及括号操作,能实现简单的计算器功能。 1 界…

北京站圆满结束!MongoDB Developer Day上海站,周六见!

上周六 MongoDB Developer Day首站北京站 80位开发者与MongoDB一起度过了充实的一天 专题讲座➕动手实操➕专家面对面交流 从数据建模、进阶查询技巧 到Atlas搜索与向量搜索 让参会伙伴们直呼“满满的技术干货!” 全体参会者与工作人员合影 MongoDB Developer …

【unity笔记】五、UI面板TextMeshPro 添加中文字体

Unity 中 TextMeshPro不支持中文字体,下面为解决方法: 准备字体文件,从Windows系统文件的Fonts文件夹里拖一个.ttf文件(C盘 > Windows > Fonts ) 准备字库文件,新建一个文本文件,命名为“字库”&…

Vue组件化、单文件组件以及使用vue-cli(脚手架)

文章目录 1.Vue组件化1.1 什么是组件1.2 组件的使用1.3 组件的名字1.4 嵌套组件 2.单文件组件2.1 vue 组件组成结构2.1.1 template -> 组件的模板结构2.1.2 组件的 script 节点2.1.3 组件的 style 节点 2.2 Vue组件的使用步骤2.2.1 组件之间的父子关系2.2.2 使用组件的三个步…

低代码+定制:优化项目管理的新方案

引言 在当今快速变化的商业环境中,企业需要更加灵活、高效的项目管理工具。低代码平台作为一种新的开发方式,因其能够快速构建应用程序而受到广泛关注。与此同时,软件定制开发仍然是满足特定复杂需求的重要手段。在项目管理中,低代…

建筑可视化中使用云渲染的几大理由

在建筑行业中,可视化技术已成为不可或缺的一部分。无论是设计方案的展示、施工进度的模拟,还是最终效果的呈现,建筑可视化都发挥着至关重要的作用。 建筑可视化是指通过计算机技术和图形学算法,将建筑设计、规划和施工过程中的数据…

社交风潮塑造者:探索用户在Facebook的影响力

在当今数字化社会中,Facebook不仅是人们社交互动的主要平台,更是塑造社交风潮和文化趋势的重要力量。本文将从另一个角度深入探讨用户在Facebook上的影响力,探索其如何通过个人行为和互动,影响和改变社会的各个方面。 个人表达和内…

一站式企业服务平台能够帮助企业解决哪些问题?

近年来一站式企业服务平台备受区域政府及园区管理者的青睐,充当着区域政府或园区的千里眼和顺风耳,可以用来捕捉与区域经济发展相关的信息,也可以用来倾听企业的诉求,更是成为了区域深抓企业服务的多面手。 同时,一站式…

AI 卖货主播大模型:Streamer-Sales 销冠!MoneyPrinterTurbo :简直就是营销号的梦想工具!

AI 卖货主播大模型:Streamer-Sales 销冠!MoneyPrinterTurbo :简直就是营销号的梦想工具! AI 卖货主播大模型:Streamer-Sales 销冠! 项目简介 Streamer-Sales 销冠 —— 卖货主播大模型 是一个能够根据给定的商品特点从激发用户购…