当前位置: 首页 > news >正文

索引与数据结构、并行算法

3. 索引与数据结构

  • 索引类比目录:类似于书籍目录,帮助我们快速定位信息。
  • 索引的核心目的:提升数据查找效率,优化增删改查性能。
  • 实际应用广泛:MySQL、Redis、搜索引擎、分布式系统、中间件等。

3.1. 索引设计中的需求分析

1. 功能性需求

考虑因素

说明

数据结构化

是结构化数据(如表格)还是非结构化数据(如网页)?

数据动态性

是静态集合还是需要支持动态增删改查?

存储位置

存储在内存 or 磁盘 or 内存+磁盘混合?

查找类型

单值查找 or 区间查找?

查询组合

单关键词 or 多关键词组合?

2. 非功能性需求

考虑因素

说明

存储空间占用

特别是内存中索引的体积控制至关重要。

索引维护成本

动态更新带来的性能负担不容忽视。

3.2. 常用索引数据结构与场景分析

1. 散列表(Hash Table)

  • 特点:查询效率高(O(1)),适合内存存储。
  • 代表应用:Redis、Memcache。
  • 限制:不支持区间查找,键需可哈希。
  1. 红黑树(Red-Black Tree)
  • 特点:自平衡 BST,支持动态数据操作(O(logn))。
  • 代表应用:Linux Ext 文件系统的块索引。
  • 适用场景:内存中的有序索引场景。

2. B+ 树

  • 特点:适合磁盘存储、节点多叉、树高低、IO 次数少。
  • 代表应用:MySQL、Oracle 数据库索引。
  • 优点:高性能磁盘查找、支持范围查询。
  • 缺点:实现复杂、维护成本高。

3. 跳表(Skip List)

  • 特点:查询效率接近平衡树,支持动态操作。
  • 代表应用:Redis 的 zset(有序集合)。
  • 优点:实现简单、灵活调整空间效率。
  • 缺点:最坏时间复杂度仍是 O(n)。

4. 位图(Bitmap)

  • 特点:适合标记“存在/不存在”状态,支持快速定位。
  • 应用场景:辅助索引、去重、统计频率。

5. 布隆过滤器(Bloom Filter)

  • 特点:高效、占用空间少,判断“不存在”很准。
  • 应用场景:提前过滤不在磁盘的数据,减少无效查询。
  • 限制:存在误判(可能误报“存在”)。

6. 有序数组

  • 特点:适用于静态数据,支持快速二分查找。
  • 适用场景:查询频繁但不更新的数据集合。
  • 限制:不支持动态插入删除。

应用场景对比总结:

数据结构

适用场景

优势

劣势

散列表

内存中的KV存储(如Redis)

查询快,O(1)

不支持区间查找

红黑树

内存中的有序数据索引

平衡查找,O(logn)

深度可能较大

B+树

磁盘中的数据库索引

多叉、低树高、IO少

实现复杂

跳表

有序集合,如Redis zset

简单灵活

查询不稳定

位图

存在性标记、状态判断

空间小,效率高

适用范围有限

布隆过滤器

过滤“不存在”的数据

高效省内存

有误判,不可删除

有序数组

静态数据、查找密集

二分查找快

插入删除代价高

4. 并行算法

4.1. 并行算法概述

  • 目的:当算法无法继续优化(例如已是 O(nlogn) 级别)时,仍可通过并行处理来显著提高执行效率
  • 本质:通过“数据分片 + 多线程并行执行”的策略,加快整体处理速度。

注意:时间复杂度 ≠ 实际性能。实际开发中,哪怕提升 10%-20%,也非常有意义。

  • 核心思想:数据分片 + 并行执行
  • 适用范围
    • 无依赖关系或依赖关系可控的任务
    • 数据规模巨大(超内存或高 I/O 需求)
  • 工程意义
    • 并行算法是一种工程优化思想,可结合多核资源提升性能
    • 如 MapReduce 就是经典的并行计算框架

4.2. 典型应用场景与改造方式

1. 并行排序

场景:排序 8GB 数据,单机内存可容纳

方案一:并行归并排序

  • 将数据划分为 16500MB 小集合
  • 16 个线程并行排序
  • 最后将 16 个有序小集合合并为一个大集合

方案二:并行快速排序

  • 扫描一遍数据,划分成 16 个有序区间
  • 每个区间用单独线程排序
  • 排完即为整体有序,无需额外合并

对比总结:

类型

特点

并行归并

先分片,后合并

并行快排

先分区间,后排序,无需合并

  • 本质都基于“分治 + 并行”的思想
  • 若数据规模为 1TB,关键变为减少磁盘 I/O 操作,而不是 CPU 执行效率。

2. 并行查找(散列表优化)

背景问题:

  • 散列表动态扩容慢、耗内存(如将 2GB 扩到 3GB,利用率低)

优化策略:

  • 将数据随机分成 k=16 份,每份构建一个小散列表
  • 优点:
    • 每个小散列表内存更易管理
    • 扩容时只需局部扩容(如 150MB 扩到 225MB)
    • 并行查找:启动 16 个线程同时搜索 16 个小散列表
    • 查找效率可能更高
    • 添加新数据时放入装载因子最小的散列表以降低冲突率

3. 并行字符串匹配

场景:

  • 关键词搜索在超大文本中非常耗时

优化方案:

  • 将大文本划分为 k=16 份,启动 16 个线程并行匹配关键词

细节处理:

  • 跨分片的关键词可能被分割(匹配失败)
  • 解决方式:
    • 关键词长度为 m
    • 每两个分片间拼接边缘 2m 长度的新串,再额外查找一次

4. 并行广度优先搜索(Parallel BFS)

原理:

  • BFS 本身是“逐层搜索”,适合并行

并行改造:

  • 使用两个队列 A、B
    1. 并行扩展 A 中所有节点 → 结果放入 B
    2. 清空 A,再并行扩展 B 中节点 → 放入 A
    3. 如此交替,直到搜索结束

相关文章:

索引与数据结构、并行算法

3. 索引与数据结构 索引类比目录:类似于书籍目录,帮助我们快速定位信息。索引的核心目的:提升数据查找效率,优化增删改查性能。实际应用广泛:MySQL、Redis、搜索引擎、分布式系统、中间件等。 3.1. 索引设计中的需求…...

GC全场景分析

GC全场景分析 文章目录 GC全场景分析标记-清除法**标记 - 清除法核心流程与 STW 机制****标记 - 清除法四步流程****1. STW 启动(暂停用户线程)****2. 标记可达对象(从根集合出发)****3. 清除未标记对象(回收堆内存&am…...

OSI七层模型和TCP/IP的五层(四层模型)

分层 1.什么是分层 我理解是对同一相同或者相似的事务或者操作功能进行分类,比如我们去餐厅吃饭,就可以分为好多层,客户层,服务员层,前台层,后厨层,每一层都专注自己的事情,客户层…...

MouseDown,MouseUp,LostMouseCapture的先后顺序

本文目标是实现如下功能: 按下一个按钮后置位某变量;鼠标松开后复位某个变量? 看似简单,但是一般来说会存在如下两种现象: 鼠标移出按钮:默认会丢失鼠标事件跟踪,即MouseLeftButtonUp事件并不会被触发。 焦点切换:Tab 键切换焦点会干扰按钮的事件捕获 本文通过几个…...

第8章 常用实用类

8.1 String类 在java.lang包(默认引入)中,可直接使用。 定义为final类,不能扩展String类,不可以继承,不可以有子类。 8.1.1 构造String对象 常量对象: 英文双引号括起来 String常量放入常…...

视差场(disparity field)

视差场(disparity field)是立体视觉中的一个重要概念,用于描述两幅立体图像之间像素的对应关系。以下是对视差场的详细解释: 1. 视差(Disparity)的定义 视差是指同一场景点在两幅立体图像中的像素位置差异…...

AI:OpenAI论坛分享—《AI重塑未来:技术、经济与战略》

AI:OpenAI论坛分享—《AI重塑未来:技术、经济与战略》 导读:2025年4月24日,OpenAI论坛全面探讨了 AI 的发展趋势、技术范式、地缘政治影响以及对经济和社会的广泛影响。强调了 AI 的通用性、可扩展性和高级推理能力,以…...

【已经解决诸多问题】Mamba安装

mamba被称为新一代的计算架构,因此在CV和时序领域存在诸多的方案开始采用这一新架构,但是这个架构的安装过程中存在诸多问题!!!!为了更好帮助大家理解我们给出一个统一的安装流程!!&…...

计算机的基本组成与性能

1. 冯诺依曼体系结构:计算机组成的金字塔 1.1. 计算机的基本硬件组成 1.CPU - 中央处理器(Central Processing Unit)。 2.内存(Memory)。 3.主板(Motherboard)。主板的芯片组(Ch…...

“绿色邮政,智能九识”——呼和浩特邮政无人快递车发车,驶向智慧物流新时代!

5月12日,“绿色邮政,智能九识”呼和浩特邮政无人驾驶快递车发车。 此次投运的邮政无人驾驶快递车实力惊人:单车运量超1000件,时速达40公里,通过智能路径规划实现24小时作业,与传统运输相比,运转…...

AGI大模型(24):通过LangChain的接口来调用OpenAI对话

1 创建对话 使用langchain库中的ChatOpenAI类来创建一个对话模型。 from dotenv import load_dotenvload_dotenv()import os from langchain_openai import ChatOpenAIllm = ChatOpenAI(api_key=os.getenv("DEEPSEEK_API_KEY"),base_url="https://api.deepsee…...

大模型中的Token机制深度解析

目录 大模型中的Token机制深度解析 一、Token的本质与核心作用 二、主流分词算法对比 三、GPT-3分词机制详解 四、分词策略对模型性能的影响 五、工程实践建议 六、未来演进方向 一、Token的本质与核心作用 Token是大模型处理文本的​​最小语义单元​​,类似于人类语…...

【MySQL】库与表的操作

一、库的操作 1. 查看数据库 语法:show databases;这里的database是要加s的 查看当前自己所处的数据库:select database(); 例如下图,我当前所处的数据库就是在class1数据库 2. 创建数据库 语法:create database [if not e…...

创建指定版本的vite项目

1、获取vite的版本号 npm view create-vite versions 注:4.4.1版本即对应着node16版本的项目 2、创建制定版本的vite项目 npm init vite<version>...

java中的Servlet3.x详解

Servlet 3.x 是 Java Web 开发的重要里程碑&#xff0c;包含 Servlet 3.0&#xff08;2009年发布&#xff09;和 Servlet 3.1&#xff08;2013年发布&#xff09;两个主要版本。它通过多项革新优化了开发效率、性能及扩展性&#xff0c;成为现代 Java Web 应用的核心技术基础。…...

单目测距和双目测距 bev 3D车道线

单目视觉测距原理 单目视觉测距有两种方式。 第一种&#xff0c;是通过深度神经网络来预测深度&#xff0c;这需要大量的训练数据。训练后的单目视觉摄像头可以认识道路上最典型的参与者——人、汽车、卡车、摩托车&#xff0c;或是其他障碍物&#xff08;雪糕桶之类&#xf…...

weibo_comment_pc_tool | 我于2025.5月用python开发的评论采集软件,根据帖子链接爬取评论的界面工具

本工具仅限学术交流使用&#xff0c;严格遵循相关法律法规&#xff0c;符合平台内容的合法及合规性&#xff0c;禁止用于任何商业用途&#xff01; 一、背景分析 1.1 开发背景 微博&#xff08;以下简称wb&#xff09;是国内极具影响力的社交媒体平台&#xff0c;具有内容形式…...

ubuntu防火墙命令和放行ssh端口

一、关闭UFW防火墙&#xff08;Ubuntu默认工具&#xff09; 1. 临时关闭防火墙 sudo ufw disable sudo ufw status # 显示 Status: inactive 表示已关闭 2. 永久禁用防火墙&#xff08;禁用系统服务&#xff09; sudo systemctl stop ufw # 立即停止服务 sudo sy…...

PWM讲解+STM32任意频率、占空比、脉宽生成函数介绍

1.PWM讲解 脉冲宽度调制(PWM)&#xff0c;是英文“Pulse Width Modulation”的缩写&#xff0c;简称脉宽调制。 脉宽调制 最开始使用PWM时&#xff0c;是做智能车时使用的舵机打角&#xff0c;电机驱动。这都属于比较浅显&#xff0c;普通的应用。下面和大家简单分享一下PWM的…...

C++23 范围迭代器作为非范围算法的输入 (P2408R5)

文章目录 一、引言二、C23及范围迭代器的背景知识2.1 C23概述2.2 范围迭代器的概念 三、P2408R5提案的内容3.1 提案背景3.2 提案内容 四、范围迭代器作为非范围算法输入的优势4.1 代码简洁性4.2 提高开发效率4.3 更好的兼容性 五、具体的代码示例5.1 使用范围迭代器进行并行计算…...

CVE-2018-1273 漏洞深度分析

漏洞概述 CVE-2018-1273 是 Spring Data Commons 中的一个高危远程代码执行&#xff08;RCE&#xff09;漏洞&#xff0c;影响版本为 Spring Data Commons 1.13–1.13.10 和 2.0–2.0.5。攻击者通过构造包含恶意 SpEL表达式的 HTTP 请求参数&#xff0c;触发表达式注入&#x…...

C++23:修正常量迭代器、哨兵和范围

文章目录 引言C20范围库回顾C23之前常量迭代器的问题视图可能不传播const代理对象的复杂性泛型代码中的一致性 P2278R4提案及C23的改进std::views::as_const的工作原理代码示例 浅const视图&#xff08;如std::span&#xff09;的改进总结 引言 在C的发展历程中&#xff0c;每…...

【漫话机器学习系列】266.雅可比矩阵(Jacobian Matrix)

雅可比矩阵&#xff08;Jacobian Matrix&#xff09;详解 | 多变量函数微积分的基石 在深度学习、计算图、优化算法、机器人控制、流形学习等众多领域中&#xff0c;“雅可比矩阵&#xff08;Jacobian Matrix&#xff09;”是一个非常核心的数学工具。 这篇文章将结合一张视觉…...

Leetcode 3551. Minimum Swaps to Sort by Digit Sum

Leetcode 3551. Minimum Swaps to Sort by Digit Sum 1. 解题思路2. 代码实现 题目链接&#xff1a;3551. Minimum Swaps to Sort by Digit Sum 1. 解题思路 这一题思路上我实现的非常暴力&#xff0c;就是先求出正确的排列&#xff0c;然后从头考察每一个元素是否处在其目标…...

西门子1200/1500博图(TIA Portal)寻址方式详解

西门子博图&#xff08;TIA Portal&#xff09;是西门子公司推出的自动化工程软件平台&#xff0c;广泛应用于工业自动化领域。在编写PLC程序时&#xff0c;寻址方式是一个非常重要的概念&#xff0c;它决定了如何访问和操作PLC中的数据和资源。本文将详细介绍西门子博图中的寻…...

STK手动建链+matlab联调

在右边场景区选择你要建链的卫星&#xff0c;右键在弹出的选项中选择Access 选择你要建链的卫星&#xff0c;这里我选择3轨10星与4轨8星建链&#xff0c;点击compute后再close就行了 建链完成&#xff0c;这里链路的颜色跟起始卫星的颜色一致&#xff0c;要想改变颜色只需改变卫…...

MATLAB中的Switch语句讲解

MATLAB中的Switch语句&#xff1a;一个简单的控制流工具 在MATLAB中&#xff0c;switch语句是一种多分支控制结构&#xff0c;通常用于根据某个表达式的值选择不同的代码块进行执行。它的作用类似于一系列的if-elseif-else语句&#xff0c;但在处理多个条件时&#xff0c;swit…...

【SpringBoot】✈️整合飞书群机器人发送消息

&#x1f4a5;&#x1f4a5;✈️✈️欢迎阅读本文章❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;本篇文章阅读大约耗时3分钟。 ⛳️motto&#xff1a;不积跬步、无以千里 &#x1f4cb;&#x1f4cb;&#x1f4cb;本文目录如下&#xff1a;&#x1f381;&#x1f381;&am…...

上位机知识篇---流式Web服务器模式的实现

文章目录 前言 前言 本文简单介绍了流式Web服务器模式的实现。...

Go 语言中的一等公民(First-Class Citizens)

在 Go 语言中&#xff0c;一等公民&#xff08;First-Class Citizens&#xff09; 是指语言中可以像普通值一样被自由操作的元素&#xff0c;包括赋值、传递、返回等。Go 虽然不是纯粹的函数式语言&#xff0c;但支持多种一等公民&#xff0c;以下是 Go 中常见的 一等公民及其特…...

python3.13版本降为3.12

目录 一、下载Python 二、安装PyCharm 三、 彩蛋 粗糙理解&#xff1a; PyThon是编译器&#xff08;也可以在命令行编辑&#xff0c;但是麻烦&#xff09; PyCharm是编辑器 一、下载Python https://repo.huaweicloud.com/python/3.12.9/python-3.12.9-amd64.exe 点击Insta…...

Ubuntu搭建TFTP服务器的方法

0 工具 Ubuntu 18.041 Ubuntu搭建TFTP服务器的方法 在Ubuntu下搭建TFTP服务器可以让我们下载文件到开发板更加方便&#xff0c;同时也可以实现TFTP加载Linux镜像&#xff0c;方便调试。 1.1 安装tftp-hpa&#xff08;TFTP客户端&#xff09;、tftpd-hpa&#xff08;TFTP服务…...

【AI】Ubuntu 22.04 4060Ti16G 基于SWIFT框架的LoRA微调 模型Qwen3-1.8B 数据集弱智吧 微调笔记

下载Qwen3-1.8B 先更新安装modescope&#xff0c;然后下载模型 pip install -U modelscope modelscope download --model Qwen/Qwen3-1.7B 下载日志 部署模型 参考&#xff1a;【AI】Ubuntu 22.04 4060Ti 16G vllm-api部署Qwen3-8B-FP8_wsl ubantu rtx4060 vllm镜像-CSDN博…...

系分论文《论信息系统缓存的分析和应用》

【摘要】 2023年3月,我作为系统分析师参与了某大型电商平台"云端购物中心"的性能优化项目。该项目日均订单量突破200万,但在促销高峰期频繁出现系统响应迟缓、数据库过载等问题。本项目以构建多级缓存体系为核心,通过系统化分析缓存应用场景和技术选型,重构了平…...

3.4/Q2,Charls最新文章解读

文章题目&#xff1a;Associations between reversible and potentially reversible cognitive frailty and falls in community-dwelling older adults in China: a longitudinal study DOI&#xff1a;10.1186/s12877-025-05872-2 中文标题&#xff1a;中国社区老年人可逆性和…...

Bash fork 炸弹 —— :(){ :|: };:

&#x1f9e0; 什么是 Fork 炸弹&#xff1f; Fork 炸弹是一种拒绝服务&#xff08;DoS&#xff09;攻击技术&#xff0c;利用操作系统的 fork() 系统调用不断创建新进程&#xff0c;直到系统资源&#xff08;如进程表、CPU、内存&#xff09;被耗尽&#xff0c;从而使系统无法…...

HarmonyOS AVPlayer 音频播放器

鸿蒙文档中心&#xff1a;使用AVPlayer播放视频(ArkTS)文档中心https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/video-playback 这张图描述的是 HarmonyOS AVPlayer 音频播放器的状态流转过程&#xff0c;展示了 AVPlayer 在不同状态之间的切换条件和关键操作…...

symfonos: 2靶场

symfonos: 2 来自 <https://www.vulnhub.com/entry/symfonos-2,331/> 1&#xff0c;将两台虚拟机网络连接都改为NAT模式 2&#xff0c;攻击机上做namp局域网扫描发现靶机 nmap -sn 192.168.23.0/24 那么攻击机IP为192.168.23.182&#xff0c;靶场IP192.168.23.253 3&…...

微服务项目->在线oj系统(Java版 - 2)

相信自己,终会成功 微服务代码: lyyy-oj: 微服务 接口文档定义 响应数据定义: 响应数据格式:通常&#xff0c;HTTP API 的响应数据采用 JSON 格式 例如:成功响应&#xff08;带数据&#xff09; {"code": 200,"message": "查询成功","…...

整理了 2009 - 2025 年的【199 管综真题 + 解析】PDF,全套共 34 份文件

每年真题原卷 ✅ 每年详细解析 ✅ &#x1f4c2;【管综真题 2009-2025】 &#x1f4c2;【管综解析 2009-2025】 目录树&#xff1a; ├── 2009-2025管综真题 PDF │ ├── 2009年199管综真题.pdf │ ├── 2010年199管综真题.pdf │ ├── 2011年199管综真题.pd…...

HarmonyOS 与 OpenHarmony:同根而不同途

HarmonyOS 与 OpenHarmony&#xff1a;同根而不同途 引言 在操作系统领域&#xff0c;HarmonyOS 和 OpenHarmony 这两个名字频繁出现&#xff0c;它们之间既存在着千丝万缕的联系&#xff0c;又有诸多显著的区别。对于开发者和相关从业者而言&#xff0c;深入了解两者的差异点…...

并发编程(4)

final修饰 1. 用final修饰类 当一个类被final修饰时&#xff0c;意味着它不能被其他类继承&#xff0c;也就是该类无法派生出子类。像 Java 中的String类就是典型的final类。 public final class FinalClass {// 类的内容 }// 下面的代码会报错&#xff0c;因为FinalClass不…...

合并K个升序链表

目录 合并 K 个升序链表 解题思路 ListNode 数组方式给出 k 个链表 ArrayList 方式给出 k 个链表 ArrayList常见操作 合并 K 个升序链表 题目描述 给你一个链表数组&#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中&#xff0c;返回合并后…...

UART、SPI、IIC复习总结

一、UART 1、UART和USART的异同&#xff1f; 相同点 基本功能&#xff1a;都是用于串行通信的数据收发设备&#xff0c;能够实现数据在不同设备之间的传输。在异步通信模式下&#xff0c;二者的工作方式相似&#xff0c;都使用起始位、数据位、校验位&#xff08;可选&#…...

【AWS入门】Amazon Bedrock简介

【AWS入门】Amazon Bedrock简介 [AWS Essentials] Brief Introduction Amazon Bedrock By JacksonML 1. 引言 Amazon Bedrock&#xff0c;在AWS官网&#xff0c;映入眼帘的第一句话就是&#xff0c;“使用基础模型构建和扩展生成式人工智能应用程序的最简单方法”。如下图所…...

报告精读:华为2024年知行合一通信行业数据治理实践指南报告【附全文阅读】

《华为 2024 年知行合一通信行业数据治理实践指南报告》聚焦通信行业数据治理&#xff0c;指出在数字化转型背景下&#xff0c;通信行业面临数据量庞大、类型多样、时效要求高、价值密度低、安全要求高等特点与数据质量、汇聚、开放等难点。报告提出通信行业数据治理需构建包含…...

Eigen与OpenCV矩阵操作全面对比:最大值、最小值、平均值

功能对比总表 功能Eigen 方法OpenCV 方法主要区别最大值mat.maxCoeff(&row, &col)cv::minMaxLoc(mat, NULL, &maxVal, NULL, &maxLoc)Eigen需要分开调用&#xff0c;OpenCV一次获取最小值mat.minCoeff(&row, &col)cv::minMaxLoc(mat, &minVal, NU…...

机器学习(12)——LGBM(1)

文章目录 LightGBM算法详解1. 算法背景2. 核心创新2.1 基于直方图的决策树算法2.2 单边梯度采样(GOSS)2.3 互斥特征捆绑(EFB) 3. 算法细节3.1 树生长策略3.2 特征并行与数据并行3.3 类别特征处理 4. 关键参数说明4.1 核心参数4.2 控制速度参数4.3 控制过拟合参数 5. 与XGBoost对…...

深入理解TCP与UDP:协议对比、头部结构与连接管理

一、TCP与UDP的核心区别 特性TCPUDP连接特性面向连接&#xff08;三次握手建立连接&#xff09;无连接&#xff0c;直接传输数据可靠性通过确认重传、排序、流控保证可靠尽力交付&#xff0c;不保证数据到达流量控制支持滑动窗口机制调节发送速率不支持数据分段支持大数据分段…...

Flask快速入门和问答项目源码

Flask基础入门 源码&#xff1a; gitee&#xff1a;我爱白米饭/Flask问答项目 - 码云 目录 1.安装环境2.【debug、host、port】3.【路由params和query】4.【模板】5.【静态文件】6.【数据库连接】6.1.安装模块6.2.创建数据库并测试连接6.3.创建数据表6.4.ORM增删改查 6.5.ORM模…...