探究MySQL中的“树”结构

1 引言

树高千丈,叶落求索 – 唐代杜牧

树结构在MySQL中常用于表示层次关系,如组织结构或分类体系。引入树结构可使数据之间建立父子关系,便于查询和管理。益处包括快速检索子节点、方便展示层次关系、支持递归查询等。

2 基础概念

2.1 名词解析

程序就像是一张有向图,你需要跟着边走才能找到正确的路径。

  • 节点(Node):图中的基本元素,通常用来表示实体或对象。在计算机科学中,节点可以是任何数据结构中的元素,如树中的节点或图中的顶点。
  • 边(Edge):节点之间的连接关系,用来表示节点之间的关联或连接。在图论中,边可以是有向的(箭头表示方向)或无向的(双向连接)。
  • 路径(Paths):在图论中,路径是图中节点的序列,其中相邻节点通过边相连。路径可以是简单路径(不经过重复节点)或环路(起点和终点相同的路径)。
  • 循环(Cycles):循环是图中形成闭合回路的路径,即起点和终点相同的路径。循环可以是简单循环(不经过重复节点,除起点和终点外)或包含重复节点的循环。
  • 稀疏度(Sparsity):是指图中边的数量与可能存在的最大边数之间的比率。在稀疏图中,边的数量相对较少,而在稠密图中,边的数量相对较多。这个概念通常用于描述图的结构和连接性。
  • 图遍历(Traversing graphs): 图遍历是一种算法,用于访问图中的所有节点或特定节点,以便对图进行分析或搜索。常见的图遍历算法包括深度优先搜索(DFS)和广度优先搜索(BFS)。DFS沿着图的深度遍历节点,而BFS则逐层遍历节点。这些算法在解决许多图相关问题时非常有用,如寻找路径、检测环路、拓扑排序等。
  • 树(Trees):树是一种层次性的数据结构,由节点(顶点)和边组成,其中每个节点最多有一个父节点,但可以有多个子节点。树的一个节点称为根节点,它没有父节点。树中除了根节点外,每个节点都有且仅有一个父节点。树的节点之间通过边连接,形成层次结构,从根节点到任意节点都有唯一的路径。树常用于表示层次关系,如组织结构、文件系统等。树的一些重要概念包括深度(节点到根节点的距离)、高度(树的最大深度)、叶节点(没有子节点的节点)等。树还有许多变种,如二叉树(每个节点最多有两个子节点)、二叉搜索树(左子节点小于父节点,右子节点大于父节点)等,它们在不同场景下有不同的应用和特性。
  • 欧拉路径(Euler Paths):欧拉路径是指在图论中,经过图中每条边恰好一次的路径。如果一个图包含欧拉路径,则称该图具有欧拉路径性质。欧拉路径可以从一个节点出发,经过每条边一次且仅一次,最终回到另一个节点,或者以某个节点结束而不回到起点。欧拉路径在解决一些图相关问题时非常有用,如在网络中找到一条包含所有边的路径,或者在游戏中找到一条经过所有关键点的路径。欧拉路径的存在性和性质受到图的结构和边的连接方式的影响,因此对于不同类型的图,欧拉路径的判断和寻找方法也会有所不同。

2.2 图的模型设计

在计算机传统上,表达图的结构关系可以使用边缘列表、邻接表或邻接矩阵其中之一来体现。

边缘列表

  • 概念:边缘列表是一种简单的图表示方法,其中每条边都列为一对顶点。
  • 优点:
    易于实现和理解。
    对于边较少的稀疏图效率高。
  • 缺点:
    对于边较多的稠密图效率低。
    查找与顶点相邻的所有边可能较慢。

邻接表

  • 概念:邻接表是一种数据结构,用于表示图,其中每个顶点维护其相邻顶点的列表。
  • 优点:
    对于边较少的稀疏图效率高。
    对于稀疏图,比邻接矩阵占用更少内存。
  • 缺点:
    对于某些操作,如检查两个顶点之间是否有边,速度较慢。
    对于边较多的稠密图,需要更多内存。

邻接矩阵

  • 概念:邻接矩阵是一个二维数组,其中两个顶点之间存在边的情况用1表示。
  • 优点:
    对于边较多的稠密图效率高。
    允许快速查找边。
  • 缺点:
    对于边较少的稀疏图效率低。
    对于稀疏图,比邻接表占用更多内存。

3 基础模型

3.1 图内容

在这里插入图片描述

3.2 表结构和数据

创建表结构并且初始化数据:

CREATE TABLE nodes ( 
nodeID CHAR ( 1 ) PRIMARY KEY 
);

CREATE TABLE edges(
 childID CHAR(1) NOT NULL,
 parentID CHAR(1) NOT NULL,
 PRIMARY KEY(childID, parentID)
);

INSERT INTO nodes VALUES ('A'), ('B'), ('C'), ('D'), ('E'), ('F');
INSERT INTO edges VALUES ('A','C'), ('C','D'), ('C','F'),('B','E');

查询数据:

SELECT * FROM edges;

在这里插入图片描述

3.3 宽度优先搜索

3.3.1 编写存储过程

定义存储过程,如下:

DROP  PROCEDURE  IF  EXISTS ListReached;
DELIMITER go
CREATE PROCEDURE ListReached (IN root CHAR(1))
BEGIN
  DECLARE rows1  SMALLINT  DEFAULT  0;
  DROP TABLE  IF EXISTS reached;
	CREATE TABLE  reached (
     nodeID  CHAR(1) PRIMARY KEY
  ) ENGINE= HEAP;
	
 INSERT INTO reached VALUES ( root );
 
 SET rows1 = ROW_COUNT();
 WHILE rows1 > 0 DO
    INSERT IGNORE INTO reached  
       SELECT DISTINCT  childID FROM edges AS e 
     INNER JOIN reached AS p ON  e.parentID = p.nodeID;
     
   SET rows1 = ROW_COUNT();
   INSERT IGNORE INTO reached  
       SELECT DISTINCT  parentID FROM edges AS e 
     INNER JOIN reached AS p ON  e.childID = p.nodeID; 
   
   SET rows1 = rows1 +  ROW_COUNT();
  END WHILE;
 
 SELECT *  FROM reached;
 DROP TABLE reached; 

END;
go 

DELIMITER;

调用存储过程:

call  ListReached( 'A');

在这里插入图片描述

3.3.2 使用CTEs

从A 开始搜索:

WITH RECURSIVE cte AS (
	SELECT
		childID,
		parentID,
		1 AS LEVEL
	FROM
		edges
	WHERE
		childId = 'A' UNION ALL
	SELECT
		t.childID,
		t.parentID,
		c.LEVEL + 1
	FROM
		edges t
	

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

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

相关文章

Pipecat: 创建语音对话agent的开源框架,支持多模态!

项目简介 pipecat 是用于构建语音(和多模态)对话代理的框架。诸如私人教练、会议助理、儿童讲故事玩具、客户支持机器人、摄入流程和尖刻的社交伙伴。 看看一些示例应用: 语音代理入门 您可以开始在本地计算机上运行 Pipecat,然…

ES6-03-模版字符串、对象的简化写法

一、模版字符串 1-1、声明 反引号。 1-2、特性 1、字符串内容可以直接换行 得用号连接 2、变量拼接 现在: 二、对象的简化写法 ES6允许在大括号里面,直接写入变量和函数,作为对象的属性和方法。 let name milk;let chage function(){con…

【pip安装】YOLOv8目标检测初步上手

说明:本篇blog是关于Ultralytics官方教程的学习笔记,环境为windowsconda 1、下载安装YOLOv8 1.1 YOLOv8介绍 Ultralytics YOLOv8 是一个尖端的、最先进的(SOTA)模型,它建立在以前 YOLO 版本的成功基础之上&#xff0…

使用System-Verilog实现FPGA基于DE2-115开发板驱动HC_SR04超声波测距模块|集成蜂鸣器,led和vga提示功能

文章目录 前言一、实验原理1.1 传感器概述:1.2 传感器引脚1.3 传感器工作原理1.4 整体测距原理及编写思路 二、System-Verilog文件2.1 时钟分频(1)clk_div.sv2.2 超声波测距(1)hc_sr_trig.sv(2)…

简单聊聊分布式系统和微服务

分布式系统是由多个独立的计算机节点通过网络相互连接协作,共同完成一项或多项任务的系统。这些节点可以是服务器、个人电脑、移动设备等,它们之间通过消息传递或共享数据来协调工作,每个节点负责系统整体功能的一部分。分布式系统的关键在于…

k8s学习--k8s集群使用容器镜像仓库Harbor

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 环境 步骤一 容器镜像仓库Harbor部署二、Kubernetes集群使用harbor仓库 环境 Ip主机名cpu内存硬盘192.168.10.11master1cpu双核2G40G192.168.10.12node011cpu双核2…

网络链路层

data: 2024/5/25 14:02:20 周六 limou3434 叠甲:以下文章主要是依靠我的实际编码学习中总结出来的经验之谈,求逻辑自洽,不能百分百保证正确,有错误、未定义、不合适的内容请尽情指出! 文章目录 1.协议结构2.封装分离3.…

计算机毕业设计 | SpringBoot 房屋销售租赁平台 房屋购物网站(附源码)

1,绪论 1.1 背景调研 在房地产行业持续火热的当今环境下,房地产行业和互联网行业协同发展,互相促进融合已经成为一种趋势和潮流。本项目实现了在线房产平台的功能,多种技术的灵活运用使得项目具备很好的用户体验感。 这个项目的…

Python自动化识别与删除Excel表格空白行和列

在处理Excel数据时,经常会遇到含有空白行和空白列的情况。这些空白区域不仅占用表格显示空间,还可能导致数据分析时出现偏差,影响数据处理的效率与结果的准确性,如空白行可能干扰数据聚合操作,导致统计计数不准确&…

【嵌入式DIY实例】-OLED显示天气数据

OLED显示天气数据 文章目录 OLED显示天气数据1、硬件准备与接线2、天气数据获取准备3、代码实现在这个物联网项目中,本文将展示如何使用 ESP8266 NodeMCU (ESP-12E) Wi-Fi 开发板和 SSD1306 OLED 显示屏(12864 像素)制作一个简单的互联网气象站。 NodeMCU 从天气网站 openwe…

牛客网刷题 | BC114 圣诞树 (不理解)

目前主要分为三个专栏,后续还会添加: 专栏如下: C语言刷题解析 C语言系列文章 我的成长经历 感谢阅读! 初来乍到,如有错误请指出,感谢! 这道题没搞懂 也没找到视…

软件定义汽车,通信连接世界 | 2024汽车软件与通信大会开幕

5月28日-30日,在江苏省工业和信息化厅、智能汽车安全技术全国重点实验室指导下,由中国中检所属中国汽车工程研究院股份有限公司(下称:中国汽研)主办,中汽院(江苏)汽车工程研究院有限公司承办的2024汽车软件…

RTOS(ENV)串口DMA接收GPS数据并解析

RTOS(ENV)配置STM32串口DMA接收模式 环境: RTOS 4.0.3Keil5ENVSTm32l475 ENV配置 使能串口: 2. 使能DMA,并设置接收缓冲区大小: 创建工程 scons --targetmdk工程配置 1. 创建串口设备句柄 #define SA…

从零开始实现一个可靠、健壮的内存池

文章目录 概要 这个项目是干什么的项目所需储备知识什么是内存池 池化技术内存池内存池主要解决的问题框架设计开发计划系统测试情况遇到的主要问题和解决方法分工和协作提交仓库目录和文件描述比赛收获 概要 这个项目是干什么的 当前项目是实现一个高并发的内存池&#xff0c…

养生与健康|一起跟随林曦老师养个元气满满

暄桐是一间传统美学教育教室,创办于2011年,林曦是创办人和授课老师,教授以书法为主的传统文化和技艺,皆在以书法为起点,亲近中国传统之美,以实践和所得,滋养当下生活。    在暄桐教室的六阶…

QT 使用信号和槽,让QLabel的内容实时与QLineEdit同步,类似vue框架的双向绑定

在窗口里放置一个单行文本编辑器(QLineEdit)和一个标签控件(QLabel),实现的效果就是当编辑器的内容被编辑时,标 签控件同步显 示编辑控件里的内容 1)当 lineEdit 控件被用户编辑时,它…

边缘密度分布图 | ggExtra包/aplot拼图/ggpubr包 等的实现方法

概述:aplot 拼图效果好 根据网友探索[1],总结如下: ggExtra 包的拼图间隙有点大,图例在主图和边缘图之间,除非去掉图例,否则没法看。aplot包的默认拼图间隙很小,比较美观,图例在外…

Java——二进制原码、反码和补码

一、简要介绍 原码、反码和补码只是三种二进制不同的表示形式,每个二进制数都有这三个形式。 1、原码 原码是将一个数的符号位和数值位分别表示的方法。 最高位为符号位,0表示正,1表示负,其余位表示数值的绝对值。 例如&…

生成式AI,在云端的绽放与盛开

编辑:阿冒 设计:沐由 毫无疑问,生成式AI已然成为当今技术发展和应用创新的重要引擎之一。 过去的一年多时间里,我们每个人都在目睹和见证着生成式AI是如何以移山倒海的力量,为诸多行业带来革命性乃至颠覆性的变革&…

FS118M 单A口QC协议芯片

FS118M是一个QC快充协议芯片,FS118M可以识别插入的手机类型,选择最为合适的协议应对手机需要。USB Type-A 口的 D连接到FS118M芯片,当手机插入到 USB Type-A 口后,根据各个协议的约定,手机和FS118M之间将开始互相识别&…