algorithm - 递归查询邻接表以在 SQL 中预先排序树遍历？-6ren

algorithm - 递归查询邻接表以在 SQL 中预先排序树遍历？

转载作者：塔克拉玛干更新时间：2023-11-03 02:40:51

我正在将数据从一个数据库架构迁移到另一个数据库架构。老人schema 有一个基于邻接表的分类系统，ID、类别和 parent_id。如果一个类别低于一秒，那类别将第二个 ID 作为其父 ID。例如:

+-------------+----------------------+--------+
| category_id | name                 | parent |
+-------------+----------------------+--------+
|           1 | ELECTRONICS          |   NULL |
|           2 | TELEVISIONS          |      1 |
|           3 | TUBE                 |      2 |
|           4 | LCD                  |      2 |
|           5 | PLASMA               |      2 |
|           6 | PORTABLE ELECTRONICS |      1 |
|           7 | MP3 PLAYERS          |      6 |
|           8 | FLASH                |      7 |
|           9 | CD PLAYERS           |      6 |
|          10 | 2 WAY RADIOS         |      6 |
+-------------+----------------------+--------+

新模式有一个改进的前序树遍历算法:

+-------------+----------------------+-----+-----+
| category_id | name                 | lft | rgt |
+-------------+----------------------+-----+-----+
|           1 | ELECTRONICS          |   1 |  20 |
|           2 | TELEVISIONS          |   2 |   9 |
|           3 | TUBE                 |   3 |   4 |
|           4 | LCD                  |   5 |   6 |
|           5 | PLASMA               |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |  10 |  19 |
|           7 | MP3 PLAYERS          |  11 |  14 |
|           8 | FLASH                |  12 |  13 |
|           9 | CD PLAYERS           |  15 |  16 |
|          10 | 2 WAY RADIOS         |  17 |  18 |
+-------------+----------------------+-----+-----+

示例取自文章 Managing Hierarchical Data in MySQL .

无论如何，我有能力或编写具有递归函数的 php 脚本这会将邻接表迁移到预序树结构。基本上对于每一行，它都会插入一个空白的“rgt”值，看起来对于 child ，将函数递归地应用于他们，保持跟踪计数器的值，然后更新 'rgt' 值。

但我想在纯 SQL 中执行此操作。但是，我所知道的还不够一个立足点。对于初学者，我不知道你是否可以用递归查询，或者是否有其他方法可以做到这一点。

最佳答案

这是我得到的；这是一个示例，可以推广或适应您的情况。

首先我会建立一个邻接表(来自维基百科的语言家族数据):

CREATE TABLE IF NOT EXISTS `language_family_adj_list` (
  `language_id` int(11) NOT NULL auto_increment,
  `language` varchar(20) NOT NULL,
  `parent_id` int(11) default NULL,
  PRIMARY KEY  (`language_id`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8 AUTO_INCREMENT=41 ;


INSERT INTO `language_family_adj_list` (`language_id`, `language`, `parent_id`) VALUES
(1, 'Finno-Ugric', NULL),
(2, 'Hungarian', 1),
(3, 'Khanty', 1),
(4, 'Mansi', 1),
(5, 'Permic', 1),
(6, 'Mari', 1),
(7, 'Mordvinic', 1),
(8, 'Sami', 1),
(9, 'Baltic-Finnic', 1),
(10, 'Komi', 5),
(11, 'Komi-Permyak', 5),
(12, 'Udmurt', 5),
(13, 'Erzya', 7),
(14, 'Moksha', 7),
(15, 'Western Sami', 8),
(16, 'Eastern Sami', 8),
(17, 'Southern Sami', 15),
(18, 'Umi Sami', 15),
(19, 'Lule Sami', 15),
(20, 'Pite Sami', 15),
(22, 'Northern Sami', 15),
(23, 'Kemi Sami', 16),
(24, 'Inari Sami', 16),
(25, 'Akkala Sami', 16),
(26, 'Kildin Sami', 16),
(27, 'Skolt Sami', 16),
(28, 'Ter Sami', 16),
(29, 'Estonian', 9),
(30, 'Finnish', 9),
(31, 'Ingrian', 9),
(32, 'Karelian', 9),
(33, 'Livonian', 9),
(34, 'Veps', 9),
(35, 'Votic', 9),
(36, 'South Estonian', 29),
(37, 'Voro', 36),
(38, 'Karelian Proper', 32),
(39, 'Lude', 32),
(40, 'Olonets Karelian', 32);

这里有一个查询来演示:

mysql> SELECT t1.language AS lev1, t2.language as lev2, t3.language as lev3, t4.language as lev4, t5.language AS lev5
    -> FROM language_family_adj_list AS t1
    -> LEFT JOIN language_family_adj_list AS t2 ON t2.parent_id = t1.language_id
    -> LEFT JOIN language_family_adj_list AS t3 ON t3.parent_id = t2.language_id
    -> LEFT JOIN language_family_adj_list AS t4 ON t4.parent_id = t3.language_id
    -> LEFT JOIN language_family_adj_list AS t5 ON t5.parent_id = t4.language_id
    -> WHERE t1.parent_id IS NULL
    -> ORDER BY t1.language, t2.language, t3.language, t4.language, t5.language;
+-------------+---------------+--------------+------------------+------+
| lev1        | lev2          | lev3         | lev4             | lev5 |
+-------------+---------------+--------------+------------------+------+
| Finno-Ugric | Baltic-Finnic | Estonian     | South Estonian   | Voro | 
| Finno-Ugric | Baltic-Finnic | Finnish      | NULL             | NULL | 
| Finno-Ugric | Baltic-Finnic | Ingrian      | NULL             | NULL | 
| Finno-Ugric | Baltic-Finnic | Karelian     | Karelian Proper  | NULL | 
| Finno-Ugric | Baltic-Finnic | Karelian     | Lude             | NULL | 
| Finno-Ugric | Baltic-Finnic | Karelian     | Olonets Karelian | NULL | 
| Finno-Ugric | Baltic-Finnic | Livonian     | NULL             | NULL | 
| Finno-Ugric | Baltic-Finnic | Veps         | NULL             | NULL | 
| Finno-Ugric | Baltic-Finnic | Votic        | NULL             | NULL | 
| Finno-Ugric | Hungarian     | NULL         | NULL             | NULL | 
| Finno-Ugric | Khanty        | NULL         | NULL             | NULL | 
| Finno-Ugric | Mansi         | NULL         | NULL             | NULL | 
| Finno-Ugric | Mari          | NULL         | NULL             | NULL | 
| Finno-Ugric | Mordvinic     | Erzya        | NULL             | NULL | 
| Finno-Ugric | Mordvinic     | Moksha       | NULL             | NULL | 
| Finno-Ugric | Permic        | Komi         | NULL             | NULL | 
| Finno-Ugric | Permic        | Komi-Permyak | NULL             | NULL | 
| Finno-Ugric | Permic        | Udmurt       | NULL             | NULL | 
| Finno-Ugric | Sami          | Eastern Sami | Akkala Sami      | NULL | 
| Finno-Ugric | Sami          | Eastern Sami | Inari Sami       | NULL | 
| Finno-Ugric | Sami          | Eastern Sami | Kemi Sami        | NULL | 
| Finno-Ugric | Sami          | Eastern Sami | Kildin Sami      | NULL | 
| Finno-Ugric | Sami          | Eastern Sami | Skolt Sami       | NULL | 
| Finno-Ugric | Sami          | Eastern Sami | Ter Sami         | NULL | 
| Finno-Ugric | Sami          | Western Sami | Lule Sami        | NULL | 
| Finno-Ugric | Sami          | Western Sami | Northern Sami    | NULL | 
| Finno-Ugric | Sami          | Western Sami | Pite Sami        | NULL | 
| Finno-Ugric | Sami          | Western Sami | Southern Sami    | NULL | 
| Finno-Ugric | Sami          | Western Sami | Umi Sami         | NULL | 
+-------------+---------------+--------------+------------------+------+
29 rows in set (0.00 sec)

所以这是修改后的前序遍历树表模式:

CREATE TABLE language_family_mptt (
 language VARCHAR(30) NOT NULL,
 lft INT NOT NULL,
 rgt INT NOT NULL
) COLLATE utf8;

然后是迁移数据的递归存储过程:

TRUNCATE TABLE language_family_mptt;
SET max_sp_recursion_depth = 255;
DROP PROCEDURE IF EXISTS insert_branches;
DROP PROCEDURE IF EXISTS start_tree;
DELIMITER ~~

CREATE PROCEDURE start_tree()
BEGIN
    DECLARE language_field VARCHAR(100);
    DECLARE done INT DEFAULT 0;
    DECLARE insert_id INT;
    DECLARE source_id INT;

    DECLARE cursor1 CURSOR FOR SELECT language, language_id FROM language_family_adj_list WHERE parent_id IS NULL ORDER BY language;

    DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;

    OPEN cursor1;
    read_loop: LOOP

        SET @my_left = 1;

        FETCH cursor1 INTO language_field, source_id;
        INSERT INTO language_family_mptt ( language, lft ) VALUES ( language_field, 1 );

        CALL insert_branches( source_id );

        UPDATE language_family_mptt SET rgt = @my_left + 1 WHERE lft = 1 AND rgt = 0;

        IF done THEN
            LEAVE read_loop;
        END IF;

    END LOOP;
    CLOSE cursor1;

END; ~~

CREATE PROCEDURE insert_branches( IN source_parent_id INT )
BEGIN
    DECLARE done INT DEFAULT 0;
    DECLARE next_source_parent_id INT DEFAULT NULL;
    DECLARE orig_left INT DEFAULT NULL;
    DECLARE language_field VARCHAR(100);    
    DECLARE cursor1 CURSOR FOR SELECT language_id, language FROM language_family_adj_list WHERE parent_id = source_parent_id ORDER BY language;
    DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;

    OPEN cursor1;

    read_loop: LOOP

        FETCH cursor1 INTO next_source_parent_id, language_field;

        IF done THEN
            LEAVE read_loop;
        END IF;

        SET @my_left = @my_left + 1;

        INSERT INTO language_family_mptt ( language, lft ) VALUES ( language_field, @my_left ); 

        SET orig_left = @my_left;

        CALL insert_branches( next_source_parent_id );

        UPDATE language_family_mptt SET rgt = @my_left + 1 WHERE lft = orig_left AND rgt = 0 ;

        SET @my_left = @my_left + 1;

    END LOOP;
    CLOSE cursor1;
END; ~~

DELIMITER ;

结果如下:

mysql> SELECT CONCAT( REPEAT( ' ', (COUNT(parent.language) - 1) ), node.language) AS name FROM language_family_mptt AS node, language_family_mptt AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt GROUP BY node.language ORDER BY node.lft;
+---------------------------------+
| name                            |
+---------------------------------+
|    Finno-Ugric                  | 
|        Baltic-Finnic            | 
|            Estonian             | 
|                South Estonian   | 
|                    Voro         | 
|            Finnish              | 
|            Ingrian              | 
|            Karelian             | 
|                Karelian Proper  | 
|                Lude             | 
|                Olonets Karelian | 
|            Livonian             | 
|            Veps                 | 
|            Votic                | 
|        Hungarian                | 
|        Khanty                   | 
|        Mansi                    | 
|        Mari                     | 
|        Mordvinic                | 
|            Erzya                | 
|            Moksha               | 
|        Permic                   | 
|            Komi                 | 
|            Komi-Permyak         | 
|            Udmurt               | 
|        Sami                     | 
|            Eastern Sami         | 
|                Akkala Sami      | 
|                Inari Sami       | 
|                Kemi Sami        | 
|                Kildin Sami      | 
|                Skolt Sami       | 
|                Ter Sami         | 
|            Western Sami         | 
|                Lule Sami        | 
|                Northern Sami    | 
|                Pite Sami        | 
|                Southern Sami    | 
|                Umi Sami         | 
+---------------------------------+
39 rows in set (0.00 sec)

关于algorithm - 递归查询邻接表以在 SQL 中预先排序树遍历？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5508985/

文章推荐： algorithm - Aho-Corasick 和真子串

mysql - 同步/流式传输 MySQL 表/表(连接表)与 PostgreSQL 表/表
我有一台 MySQL 服务器和一台 PostgreSQL 服务器。需要从多个表中复制或重新插入一组数据 MySQL 流式传输/同步到 PostgreSQL 表。这种复制可以基于时间(Sync)或事
php - 从用户(表)获取数据其中用户(表)的id等于 friend (表)的id
如果两个表的 id 彼此相等，我尝试从一个表中获取数据。这是我使用的代码: SELECT id_to , email_to , name_to , status_to
sql - Excel 表 SQL 表
我有一个 Excel 工作表。顶行对应于列名称，而连续的行每行代表一个条目。如何将此 Excel 工作表转换为 SQL 表？我使用的是 SQL Server 2005。最佳答案这取决于您使用哪
mysql - 如何将两个django模型(表)合并为一个模型(表)
我想合并两个 Django 模型并创建一个模型。让我们假设我有第一个表表 A，其中包含一些列和数据。 Table A -------------- col1 col2 col3 col
mysql - 表 1、表 2 的多列左连接
我有两个表:table1，table2，如下所示 table1: id name 1 tamil 2 english 3 maths 4 science table2: p
sql - 大传感器数据最佳选择。表 SQL 与 Azure 表
关闭。此题需要details or clarity 。目前不接受答案。想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题. 已关闭 1 年前。 Improve th
dynamics-ax-2009 - 表=表与表.数据(表)
下面两个语句有什么区别？ newTable = orginalTable 或 newTable.data(originalTable) 我怀疑 .data() 方法具有性能优势，因为它在标准 AX 中
SQL Server 表 -(或可能是任何 SQL 表)没有主键会影响性能吗？
我有一个表，我没有在其中显式定义主键，它并不是真正需要的功能......但是一位同事建议我添加一个列作为唯一主键以随着数据库的增长提高性能...... 谁能解释一下这是如何提高性能的？没有使用索引(
php - 将产品详细信息插入 'product' 表，并将产品图像插入 'image' 表
如何将表“产品”中的产品记录与其不同表“图像”中的图像相关联？我正在对产品 ID 使用自动增量。我觉得不可能进行关联，因为产品 ID 是自动递增的，因此在插入期间不可用! 如何插入新产品，获取产品
python - 创建一个新的 sql 表，其中的列源自另一个 sql 表
我有一个 sql 表，其中包含关键字和出现次数，如下所示(尽管出现次数并不重要): ____________ dog | 3 | ____________ rat | 7 | ____
MySQL LAST_INSERT_ID() 与 INSERT INTO 表 SELECT FROM 表
是否可以使用目标表中的LAST_INSERT_ID更新源表？ INSERT INTO `target` SELECT `a`, `b` FROM `source` 目标表有一个自动增量键id，我想将其
mysql - 查询 - 在简单的 mysql 内连接中定义(表，表)
我正在重建一个搜索查询，因为它在“我看到的”中变得多余，我想知道什么 (albums_artists, artists) ( ) does in join? is it for boosting pe
innodb - mysqldump 备份缺少所有 innodb 表，但没有 MyISAM 表
以下是我使用 mysqldump 备份数据库的开关: /usr/bin/mysqldump -u **** --password=**** --single-transaction --databas
html - 为什么 MySQL 表中的所有行都是相同的？ (MySQL 表 > HTML 表)
我试图获取 MySQL 表中的所有行并将它们放入 HTML 表中: Exam ID Status Assigned Examiner
mysql - 查询 'photos' 表，同时查询 'bookmarks' 表，以便知道添加书签的照片
如何查询名为 photos 的表中的所有记录，并知道当前用户使用单个查询将哪些结果照片添加为书签？这是我的表格: -- -- Table structure for table `photos` -
Mysql MEMORY 表 vs InnoDB 表(很多插入，很少读取)
我的网站都在 InnoDB 表上运行，目前为止运行良好。现在我想知道在我的网站上实时发生了什么，所以我将每个页面浏览量(页面、引荐来源网址、IP、主机名等)存储在 InnoDB 表中。每秒大约有 10
mysql - 如何在 mysql 中存储客户数据(2 表 vs 1 表)
我在想我会为 mysql 准备两个表。一个用于存储登录信息，另一个用于存储送货地址。这是传统方式还是所有内容都存储在一张表中？对于两个表...有没有办法自动将表 A 的列复制到表 B，以便我可以引用
mysql - 表 1 包含名字和姓氏，表 2 包含两列引用表 1 上的名称
我不是程序员，我从这个表格中阅读了很多关于如何解决我的问题的内容，但我的搜索效果不好我有两张 table 表 1:成员 id*| name | surname -------------------
c# - 如何在 ASP.NET 中显示 "View"表(SQL 表)？
我知道如何在 ASP.NET 中显示真实表，例如 public ActionResult Index() { var s = db.StaffInfoDBSet.ToList(); r
php - INSERT INTO 表 VALUES.. 与 INSERT INTO 表 SET 错误
我正在尝试运行以下查询: "insert into visits set source = 'http://google.com' and country = 'en' and ref = '1234

塔克拉玛干

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

algorithm - 递归查询邻接表以在 SQL 中预先排序树遍历？