如何设计合理的树状结构表:平衡查询效率与维护效率
树状结构广泛应用于数据建模中,例如 商品分类、组织架构、权限管理 等场景。合理设计树形结构的数据库表,能够有效提升 查询效率 和 维护效率。本文将探讨如何在设计时平衡这两者,详细介绍常用的几种树状结构存储方式及其适用场景。
一、树状结构的常见存储方式
设计树状结构时,我们主要考虑以下几种存储方式:
- 邻接表模型(Adjacency List Model)
- 路径枚举模型(Path Enumeration Model)
- 闭包表模型(Closure Table Model)
- 左值右值模型(Nested Set Model)
每种方式在 查询效率 和 维护效率 上有不同的权衡,具体选择需结合实际业务需求。
二、四种存储方式的对比
1. 邻接表模型(Adjacency List Model)
设计
邻接表模型是树形结构最常见的一种存储方式。每个节点除了存储自己的信息外,还会存储一个指向其父节点的引用。这个模型结构简单,便于理解,适合 树结构较浅、层级较少 的场景。
CREATE TABLE Category (id INT PRIMARY KEY,name NVARCHAR(255),parent_id INT,FOREIGN KEY (parent_id) REFERENCES Category(id)
);
优缺点
- 优点:
- 插入和删除操作简单,更新操作不涉及其他节点。
- 表结构直观,易于理解和实现。
- 缺点:
- 查询某个节点的所有子节点需要递归或多次查询,效率较低。
- 查询某个节点的所有父节点比较麻烦,需要一直追溯到根节点。
- 如果树结构较深,递归查询的性能会下降。
适用场景
- 树形结构较浅(层级较少),且数据更新操作较为频繁的场景,如短期使用的分类、简单的组织架构等。
2. 路径枚举模型(Path Enumeration Model)
设计
路径枚举模型通过在每个节点中存储其路径信息来表达树形结构。路径是从根节点到当前节点的完整路径,通常以分隔符(如斜杠/)分隔。
CREATE TABLE Category (id INT PRIMARY KEY,name NVARCHAR(255),path NVARCHAR(255) -- 表示路径,如 /1/3/7/
);
优缺点
- 优点:
- 查询所有子节点非常简单,通过 路径前缀匹配 即可完成。
- 查询某个节点的所有父节点也非常直观,只需 分隔路径 获取父节点。
- 缺点:
- 插入或删除节点时,必须更新整个路径,因此对树形结构的更改操作较为复杂。
- 路径较长时,可能会影响存储效率。
适用场景
- 树形结构深度不大,且对查询效率要求较高的场景,尤其是 查询父子关系频繁 的应用场景,如文件系统管理、URL 路由管理等。
3. 闭包表模型(Closure Table Model)
设计
闭包表模型通过创建一个额外的表来记录节点与其祖先之间的关系。该表包括每个节点与所有祖先节点的关联记录,以及它们之间的深度。
CREATE TABLE Category (id INT PRIMARY KEY,name NVARCHAR(255)
);CREATE TABLE CategoryClosure (ancestor INT,descendant INT,depth INT,PRIMARY KEY (ancestor, descendant),FOREIGN KEY (ancestor) REFERENCES Category(id),FOREIGN KEY (descendant) REFERENCES Category(id)
);
优缺点
- 优点:
- 查询某个节点的所有子节点或父节点非常高效,因为可以通过简单的 区间查询 直接获取。
- 插入、删除操作的维护效率相对较高,只需要对受影响的节点进行更新。
- 能高效地处理 复杂的层级关系 和 频繁的查询需求。
- 缺点:
- 数据存储空间较大,因为每个节点都会与其祖先关系保存记录,可能会导致表膨胀。
- 插入新节点时需要维护祖先信息,操作较复杂。
适用场景
- 树形结构深度较大,对 查询性能 有较高要求,并且 更新频率较低 的场景,如复杂的权限管理、商品分类管理等。
4. 左值右值模型(Nested Set Model)
设计
左值右值模型是另一种通过区间存储树形结构的方式。每个节点通过 left_value 和 right_value 表示其在树中的位置。这两个值通过 深度优先遍历 得到,left_value 代表节点进入时的编号,right_value 代表退出时的编号。
CREATE TABLE Category (id INT PRIMARY KEY,name NVARCHAR(255),left_value INT NOT NULL,right_value INT NOT NULL
);
优缺点
- 优点:
- 查询子树非常高效,使用 区间查询 可以一次性获取所有子节点。
- 查询所有祖先节点、子节点等操作都能在 O(1) 时间内完成。
- 查询效率较高,适用于 读多写少 的场景。
- 缺点:
- 插入、删除操作相对复杂,需要 更新大量的节点,因此维护成本较高。
- 对于树形结构变动较频繁的场景,可能会出现性能瓶颈。
适用场景
- 查询为主,数据不经常变动的场景,如商品分类、树形权限管理等。特别适合 读多写少 的应用。
三、如何平衡查询效率与维护效率
1. 分析应用场景
选择哪种树状结构存储方式,首先要明确应用场景:
- 查询频繁:如复杂的 权限管理系统 或 树状报告分析。
- 更新频繁:如 实时组织架构管理 或 文件系统操作。
2. 数据的变动频率
- 如果数据变化不大,但查询需要高效,推荐 左值右值模型 或 闭包表模型。
- 如果数据变动频繁,且查询性能要求较高,推荐 邻接表模型 或 路径枚举模型。
3. 考虑存储空间
- 闭包表模型 和 左值右值模型 会占用额外的存储空间。如果存储空间紧张,可能需要优化存储,选择 邻接表模型。
四、总结与建议
树状结构在数据库设计中的选择,需要根据实际的 查询需求 和 数据变动频率 来权衡不同的存储方式。总的来说:
- 邻接表模型 适用于 层级较浅,更新频繁的场景。
- 路径枚举模型 适合 树形结构深度较大,且对查询效率要求高的场景。
- 闭包表模型 适合 树形结构复杂,并且 查询需求多 的场景。
- 左值右值模型 在 查询频繁,更新较少 的场景下表现优异,但维护成本较高。
通过合理的设计,可以在保证查询效率的同时,减少对系统维护的负担,提高树状结构表的整体性能。
相关文章:
如何设计合理的树状结构表:平衡查询效率与维护效率
树状结构广泛应用于数据建模中,例如 商品分类、组织架构、权限管理 等场景。合理设计树形结构的数据库表,能够有效提升 查询效率 和 维护效率。本文将探讨如何在设计时平衡这两者,详细介绍常用的几种树状结构存储方式及其适用场景。 一、树状…...
Springboot的简单推荐实现
以springboot 推荐社团招新为例子 使用 Spring Boot 构建社团招新推荐系统,用户注册后选择兴趣,系统根据兴趣推荐社团。 实现包括用户注册、兴趣选择和基于标签匹配的推荐算法。 系统使用 JPA 管理数据库,Spring Security 确保安全࿰…...
SpringBoot速成概括
视频:黑马程序员SpringBoot3Vue3全套视频教程,springbootvue企业级全栈开发从基础、实战到面试一套通关_哔哩哔哩_bilibili 图示:...
springboot多实例部署时,@Scheduled注释的方法重复执行
问题:springboot多实例部署时,Scheduled注释的方法重复执行 在 Spring Boot 中要实现 Redis 的SET NX EX命令,可以借助 Spring Data Redis 来完成。SET NX EX命令用于在键不存在时设置键值对,并同时设置过期时间。 <dependen…...
蓝桥杯15 填空题
1.握手问题: 思路:首先当所有人都握过手,由于一次握手相当于两个人都握手过,所以容易发现这是一个组合问题,为(50*49)/2,而其中有7个人没有相互握过手,那么减去ÿ…...
快速入门——第三方组件element-ui
学习自哔哩哔哩上的“刘老师教编程”,具体学习的网站为:10.第三方组件element-ui_哔哩哔哩_bilibili,以下是看课后做的笔记,仅供参考。 第一节 组件间的传值 组件可以有内部Data提供数据,也可由父组件通过prop方式传…...
力扣-贪心-455 分发饼干
思路 用小饼干去喂胃口小的孩子,不满足条件的时候,去喂胃口稍微大点的孩子,尽可能多满足孩子 class Solution { public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.b…...
【多模态处理篇二】【深度揭秘:DeepSeek视频理解之时空注意力机制解析】
一、为啥要搞视频理解这事儿 咱先唠唠为啥视频理解这么重要哈。现在这互联网时代,视频那可是铺天盖地的。你刷短视频平台,看在线电影,玩游戏直播,到处都是视频。但是计算机它一开始可不懂视频里到底是啥意思,它看到的就是一堆像素点和声音信号。 视频理解呢,就是要让计…...
网络运维学习笔记 017 HCIA-Datacom综合实验01
文章目录 综合实验1实验需求总部特性 分支8分支9 配置一、 基本配置(IP二层VLAN链路聚合)ACC_SWSW-S1SW-S2SW-Ser1SW-CoreSW8SW9DHCPISPGW 二、 单臂路由GW 三、 vlanifSW8SW9 四、 OSPFSW8SW9GW 五、 DHCPDHCPGW 六、 NAT缺省路由GW 七、 HTTPGW 综合实…...
数据结构:实验题目:单链表归并。将两个非递减次序排列的单链表归并为一个非递增次序排列的单链表,并计算表长。要求利用原来两个单链表的结点存放合并后的单链表。
输出样例如图: 代码如下: #include<stdio.h>#include<stdlib.h>//链表节点结构 typedefstructListNode{intval;structListNode*next; } ListNode;// 创建新节点 ListNode* createNode(int val){ListNode* newNode (ListNode*)malloc(sizeo…...
请求go构建缓存,go clean -cache
go clean -cache go 构建时会产生很多缓存, 一般是目录:/Users/xxx/Library/Caches/go-build 此目录README: This directory holds cached build artifacts from the Go build system. Run "go clean -cache" if the directory …...
Windows和Linux下,通过C++实现获取蓝牙版本号
在 C 中获取蓝牙版本号,不同的操作系统有不同的实现方式,下面分别介绍在 Windows 和 Linux 系统下的实现方法。 Windows 系统 在 Windows 系统中,可以使用 Windows API 来与蓝牙设备交互,获取蓝牙版本号。以下是一个示例代码&…...
【网络】如何划分子网、计算子网掩码、确定网络地址、广播地址和可用主机地址范围?
当然!让我们一步一步详细介绍如何划分子网、计算子网掩码、确定网络地址、广播地址和可用主机地址范围。假设我们从一个 10.0.0.0/24 的网络开始,并且需要为每个子网提供 50 个主机地址。 问题概述: 我们有一个网络 10.0.0.0/24。我们希望为…...
内核数据结构用法(2)list
list 在 Linux 内核中,链表操作是通过一组宏和函数来实现的,这些操作通常用来管理和遍历链表。以下是一些常用的链表函数和宏的具体用法。 1. 定义链表节点 首先,你需要定义一个包含 struct list_head 的结构体: #include <…...
【数据分析】2.数据分析业务全流程
业务流程方法论:3阶段6步骤 一、课程核心内容结构 1. 方法论概述 目标:系统性地解决商业中的关键问题框架:分为三个阶段,每个阶段包含两个步骤适用场景:适用于数据分析师、业务经理等需要通过数据分析支持决策的从业…...
第三十章 V - W 开头的术语
文章目录 第三十章 V - W 开头的术语视图 (view)虚拟字段 (virtual field)虚拟表 (virtual table) 以 W 开头的术语观察点 (watchpoint)Web 应用程序 (web application)工作集 (working set)写入镜像日志记录 (write image journaling) 以 X 开头的术语XData 第三十章 V - W 开…...
模拟实现Java中的计时器
定时器是什么 定时器也是软件开发中的⼀个重要组件. 类似于⼀个 "闹钟". 达到⼀个设定的时间之后, 就执⾏某个指定好的代码. 前端/后端中都会用到计时器. 定时器是⼀种实际开发中⾮常常⽤的组件. ⽐如⽹络通信中, 如果对⽅ 500ms 内没有返回数据, 则断开连接尝试重…...
Eclipse2024中文汉化教程(图文版)
对应Eclipse,部分人需要中文汉化,本章教程,介绍如何对Eclipse进行汉化的具体步骤。 一、汉化前的Eclipse 默认安装Eclipse的时候,默认一般都是English的,我当前版本是使用的是2024-06版本的Eclipse。 二、汉化详细步骤 点击上方菜单选项卡,Hep——Install New Software……...
【回溯算法2】
力扣17.电话号码的字母组合 链接: link 思路 这道题容易想到用嵌套的for循环实现,但是如果输入的数字变多,嵌套的for循环也会变长,所以暴力破解的方法不合适。 可以定义一个map将数字和字母对应,这样就可以获得数字字母的映射了…...
21.《SpringBoot 异步编程@Async与CompletableFuture》
SpringBoot 异步编程 文章导读 本文系统讲解 Spring Boot 异步编程的核心技术与实践方案,涵盖从基础使用到高级优化的全链路知识。通过深入剖析 Async 注解原理、线程池配置策略、异步异常处理机制等关键技术点,结合典型业务场景的代码示例,…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
