登录 注册

大神们，树的检索问题请教

本贴最后更新于 2944 天前，其中的信息可能已经天翻地覆

我有很多棵这样的树存储在数据库里

CREATE TABLE tree (
id int(11) NOT NULL AUTO_INCREMENT,
name varchar(20) NOT NULL,
lft int(11) NOT NULL,
rgt int(11) NOT NULL,
PRIMARY KEY (id)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

1、如何根据根结点查询出整棵树？

2、如何用 SQL 算出某一树结点的深度？

3、如何根据某一结点查询出从根结点到这棵树路径 + 深度？

4、如何查询出结点的所有直接子结点 + 深度？

8ca79fbcb662410688f1708f52af7eff.png

  • 树
    3 引用 • 39 回帖
  • 检索
    1 引用 • 9 回帖
  • 算法
    428 引用 • 254 回帖 • 24 关注
  • SQL
    127 引用 • 386 回帖 • 3 关注
北京 位置
1 关注
1 收藏
9 回帖
5
3
2.8k 15 195 702 531 362 423 555

相关帖子

9 回帖
大神们，树的检索问题请教

欢迎来到这里！

我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。

注册 关于
请输入回帖内容 ...
  • gaosheng • via macOS
    1. select t.* from tree t inner join tree root ON t.lft >= root.lft and t.rgt <= root.rgt order by t.lft asc;
    2. select count(1) from tree t inner join tree child ON t.lft <= child.lft and t.rgt >= child.rgt;
    3. select t.* from tree t inner join tree child ON t.lft <= child.lft and t.rgt >= child.rgt order by t.lft asc; 查询结果就是树路径，结果 size 就是深度
    4. 子节点查询方法跟 1 一样啊，深度建议在表中单加一字段维护
    2 回复
  • meikaiyipian •
    作者

    ON t.lft >= root.lft and t.rgt <= root.rgt 这样会查出不同树之间的结点

    c7bf91b536864eefae149c9c41de4e30.png

  • meikaiyipian •
    作者

    加上 `root.name = 'A'
    也不行

    d65d22cd4cc3422c87d136f1736618f3.png

  • eddy •
    • 按照你的表设计来看应该是二叉树，这就和你的树形结构图不符（根结点有三个树枝节点）
    • 按照你的表设计，虽然可以满足二叉树的存储，但是按照你的查询需求 SQL 会很复杂，建议表扩展一个字段，定义为当前节点的所有父节点，如 E 的父节点字段记为：A:B
      • 根结点查询出这个树是否使用新增字段均可
      • 深度使用新增字段
      • 路径使用新增字段
      • 查询子节点不需使用新增字段，查询深度使用新增节点
    1 回复
  • meikaiyipian •
    作者

    呃。。。不是二叉树，就是普通树

    1 回复
  • eddy •

    我的思路就是，不单单只存储子节点信息，同时存储父节点信息，这样无论是查找路径还是查找深度，或者是构建整棵树（从根结点由上至下构建）都会简单些

    1 回复
  • meikaiyipian •
    作者

    你的意思是再加一个字段存取父结点 `id 是吗

    1 回复
  • eddy •

    嗯，存当前节点所有父节点的 ID，如你文章中的截图，叶子节点 E 存储 父节点信息：A 和 B

    1 回复
  • meikaiyipian •
    作者

    明白了，多谢

请输入回帖内容 ...
meikaiyipian
几根瘦骨撑天地，一点寒香透古今 北京
回帖
297
 帖子
15
 积分
12592

近期热议

推荐标签 标签

  • PWA

    PWA（Progressive Web App）是 Google 在 2015 年提出、2016 年 6 月开始推广的项目。它结合了一系列现代 Web 技术，在网页应用中实现和原生应用相近的用户体验。

    14 引用 • 69 回帖 • 175 关注
  • 脑图

    脑图又叫思维导图，是表达发散性思维的有效图形思维工具 ，它简单却又很有效，是一种实用性的思维工具。

    31 引用 • 96 回帖
  • frp

    frp 是一个可用于内网穿透的高性能的反向代理应用，支持 TCP、UDP、 HTTP 和 HTTPS 协议。

    20 引用 • 7 回帖 • 3 关注
  • Caddy

    Caddy 是一款默认自动启用 HTTPS 的 HTTP/2 Web 服务器。

    12 引用 • 54 回帖 • 167 关注
  • jQuery

    jQuery 是一套跨浏览器的 JavaScript 库，强化 HTML 与 JavaScript 之间的操作。由 John Resig 在 2006 年 1 月的 BarCamp NYC 上释出第一个版本。全球约有 28% 的网站使用 jQuery，是非常受欢迎的 JavaScript 库。

    63 引用 • 134 回帖 • 737 关注
  • golang

    Go 语言是 Google 推出的一种全新的编程语言，可以在不损失应用程序性能的情况下降低代码的复杂性。谷歌首席软件工程师罗布派克（Rob Pike）说：我们之所以开发 Go，是因为过去 10 多年间软件开发的难度令人沮丧。Go 是谷歌 2009 发布的第二款编程语言。

    498 引用 • 1395 回帖 • 260 关注
  • 星云链

    星云链是一个开源公链，业内简单的将其称为区块链上的谷歌。其实它不仅仅是区块链搜索引擎，一个公链的所有功能，它基本都有，比如你可以用它来开发部署你的去中心化的 APP，你可以在上面编写智能合约，发送交易等等。3 分钟快速接入星云链 (NAS) 测试网

    3 引用 • 16 回帖 • 1 关注
  • TextBundle

    TextBundle 文件格式旨在应用程序之间交换 Markdown 或 Fountain 之类的纯文本文件时，提供更无缝的用户体验。

    1 引用 • 2 回帖 • 72 关注
  • RESTful

    一种软件架构设计风格而不是标准，提供了一组设计原则和约束条件，主要用于客户端和服务器交互类的软件。基于这个风格设计的软件可以更简洁，更有层次，更易于实现缓存等机制。

    30 引用 • 114 回帖 • 5 关注
  • NetBeans

    NetBeans 是一个始于 1997 年的 Xelfi 计划，本身是捷克布拉格查理大学的数学及物理学院的学生计划。此计划延伸而成立了一家公司进而发展这个商用版本的 NetBeans IDE，直到 1999 年 Sun 买下此公司。Sun 于次年（2000 年）六月将 NetBeans IDE 开源，直到现在 NetBeans 的社群依然持续增长。

    78 引用 • 102 回帖 • 701 关注
  • 宕机

    宕机，多指一些网站、游戏、网络应用等服务器一种区别于正常运行的状态，也叫“Down 机”、“当机”或“死机”。宕机状态不仅仅是指服务器“挂掉了”、“死机了”状态，也包括服务器假死、停用、关闭等一些原因而导致出现的不能够正常运行的状态。

    13 引用 • 82 回帖 • 74 关注
  • Markdown

    Markdown 是一种轻量级标记语言，用户可使用纯文本编辑器来排版文档，最终通过 Markdown 引擎将文档转换为所需格式（比如 HTML、PDF 等）。

    169 引用 • 1527 回帖
  • Log4j

    Log4j 是 Apache 开源的一款使用广泛的 Java 日志组件。

    20 引用 • 18 回帖 • 34 关注
  • OAuth

    OAuth 协议为用户资源的授权提供了一个安全的、开放而又简易的标准。与以往的授权方式不同之处是 oAuth 的授权不会使第三方触及到用户的帐号信息（如用户名与密码），即第三方无需使用用户的用户名与密码就可以申请获得该用户资源的授权，因此 oAuth 是安全的。oAuth 是 Open Authorization 的简写。

    36 引用 • 103 回帖 • 28 关注
  • Laravel

    Laravel 是一套简洁、优雅的 PHP Web 开发框架。它采用 MVC 设计，是一款崇尚开发效率的全栈框架。

    20 引用 • 23 回帖 • 738 关注
  • BND

    BND（Baidu Netdisk Downloader）是一款图形界面的百度网盘不限速下载器，支持 Windows、Linux 和 Mac，详细介绍请看这里。

    107 引用 • 1281 回帖 • 30 关注
  • Hadoop

    Hadoop 是由 Apache 基金会所开发的一个分布式系统基础架构。用户可以在不了解分布式底层细节的情况下，开发分布式程序。充分利用集群的威力进行高速运算和存储。

    87 引用 • 122 回帖 • 628 关注
  • Openfire

    Openfire 是开源的、基于可拓展通讯和表示协议 (XMPP)、采用 Java 编程语言开发的实时协作服务器。Openfire 的效率很高，单台服务器可支持上万并发用户。

    6 引用 • 7 回帖 • 98 关注
  • 阿里巴巴

    阿里巴巴网络技术有限公司（简称：阿里巴巴集团）是以曾担任英语教师的马云为首的 18 人，于 1999 年在中国杭州创立，他们相信互联网能够创造公平的竞争环境，让小企业通过创新与科技扩展业务，并在参与国内或全球市场竞争时处于更有利的位置。

    43 引用 • 221 回帖 • 75 关注
  • 招聘

    哪里都缺人，哪里都不缺人。

    188 引用 • 1057 回帖
  • jsoup

    jsoup 是一款 Java 的 HTML 解析器，可直接解析某个 URL 地址、HTML 文本内容。它提供了一套非常省力的 API，可通过 DOM，CSS 以及类似于 jQuery 的操作方法来取出和操作数据。

    6 引用 • 1 回帖 • 490 关注
  • 笔记

    好记性不如烂笔头。

    311 引用 • 796 回帖
  • Ruby

    Ruby 是一种开源的面向对象程序设计的服务器端脚本语言，在 20 世纪 90 年代中期由日本的松本行弘（まつもとゆきひろ/Yukihiro Matsumoto）设计并开发。在 Ruby 社区，松本也被称为马茨（Matz）。

    7 引用 • 31 回帖 • 252 关注
  • iOS

    iOS 是由苹果公司开发的移动操作系统，最早于 2007 年 1 月 9 日的 Macworld 大会上公布这个系统，最初是设计给 iPhone 使用的，后来陆续套用到 iPod touch、iPad 以及 Apple TV 等产品上。iOS 与苹果的 Mac OS X 操作系统一样，属于类 Unix 的商业操作系统。

    87 引用 • 139 回帖 • 1 关注
  • 小薇

    小薇是一个用 Java 写的 QQ 聊天机器人 Web 服务，可以用于社群互动。

    由于 Smart QQ 从 2019 年 1 月 1 日起停止服务，所以该项目也已经停止维护了！

    34 引用 • 467 回帖 • 759 关注
  • Vditor

    Vditor 是一款浏览器端的 Markdown 编辑器，支持所见即所得、即时渲染（类似 Typora）和分屏预览模式。它使用 TypeScript 实现，支持原生 JavaScript、Vue、React 和 Angular。

    364 引用 • 1840 回帖 • 3 关注
  • Bootstrap

    Bootstrap 是 Twitter 推出的一个用于前端开发的开源工具包。它由 Twitter 的设计师 Mark Otto 和 Jacob Thornton 合作开发，是一个 CSS / HTML 框架。

    18 引用 • 33 回帖 • 660 关注

最新标签