mysql 邻接表,MySQL-邻接表模型-获取深度

逃离我推掉我的手 2023-01-24 03:30 44阅读 0赞

![Image 1][]

I have an organization table that has an id, a parent\_id, and a name column. There are roughly 50k rows in this table. There is just one top level parent and the rest are all under that. In Oracle, I am able to easily retrieve the current depth of a particular organization with the level pseudocolumn:

SELECT id, parent\_id, level, name

FROM organizations

START WITH parent\_id = 1

CONNECT BY PRIOR id = parent\_id

I am at a loss of what the proper way to do the above in MySQL is. I need to fetch the entire tree along with the node's depth in one query.

There are a plethora of questions on StackOverflow that have to do with this, but none of them seem to have a really good answer to it, mostly links to blogs with dubious solutions. Surely this is doable in some sort of straight-forward manner?

Unfortunately modifying the table in any way is not an option, so nested sets is not a possibility.

解决方案

This is totally hilarious. I just picked up a +50 bounty on a similar question literally yesterday : Using MySQL query to traverse rows to make a recursive tree

I will post the same stored procedures along with the examples from my DBA StackExchange answer:

Code to Get the Parent for Any Given Node

DELIMITER $$

DROP FUNCTION IF EXISTS \`junk\`.\`GetParentIDByID\` $$

CREATE FUNCTION \`junk\`.\`GetParentIDByID\` (GivenID INT) RETURNS INT

DETERMINISTIC

BEGIN

DECLARE rv INT;

SELECT IFNULL(parent\_id,-1) INTO rv FROM

(SELECT parent\_id FROM pctable WHERE id = GivenID) A;

RETURN rv;

END $$

DELIMITER ;

Code to Get the Ancenstry for Any Given Node

DELIMITER $$

DROP FUNCTION IF EXISTS \`junk\`.\`GetAncestry\` $$

CREATE FUNCTION \`junk\`.\`GetAncestry\` (GivenID INT) RETURNS VARCHAR(1024)

DETERMINISTIC

BEGIN

DECLARE rv VARCHAR(1024);

DECLARE cm CHAR(1);

DECLARE ch INT;

SET rv = '';

SET cm = '';

SET ch = GivenID;

WHILE ch > 0 DO

SELECT IFNULL(parent\_id,-1) INTO ch FROM

(SELECT parent\_id FROM pctable WHERE id = ch) A;

IF ch > 0 THEN

SET rv = CONCAT(rv,cm,ch);

SET cm = ',';

END IF;

END WHILE;

RETURN rv;

END $$

DELIMITER ;

Code to Get the Family Tree (or Descendants) for Any Given Node

DELIMITER $$

DROP FUNCTION IF EXISTS \`junk\`.\`GetFamilyTree\` $$

CREATE FUNCTION \`junk\`.\`GetFamilyTree\` (GivenID INT) RETURNS varchar(1024) CHARSET latin1

DETERMINISTIC

BEGIN

DECLARE rv,q,queue,queue\_children VARCHAR(1024);

DECLARE queue\_length,front\_id,pos INT;

SET rv = '';

SET queue = GivenID;

SET queue\_length = 1;

WHILE queue\_length > 0 DO

SET front\_id = FORMAT(queue,0);

IF queue\_length = 1 THEN

SET queue = '';

ELSE

SET pos = LOCATE(',',queue) + 1;

SET q = SUBSTR(queue,pos);

SET queue = q;

END IF;

SET queue\_length = queue\_length - 1;

SELECT IFNULL(qc,'') INTO queue\_children

FROM (SELECT GROUP\_CONCAT(id) qc

FROM pctable WHERE parent\_id = front\_id) A;

IF LENGTH(queue\_children) = 0 THEN

IF LENGTH(queue) = 0 THEN

SET queue\_length = 0;

END IF;

ELSE

IF LENGTH(rv) = 0 THEN

SET rv = queue\_children;

ELSE

SET rv = CONCAT(rv,',',queue\_children);

END IF;

IF LENGTH(queue) = 0 THEN

SET queue = queue\_children;

ELSE

SET queue = CONCAT(queue,',',queue\_children);

END IF;

SET queue\_length = LENGTH(queue) - LENGTH(REPLACE(queue,',','')) + 1;

END IF;

END WHILE;

RETURN rv;

END $$

To demonstrate the execution of everything, here is the sample data

USE junk

DROP TABLE IF EXISTS pctable;

CREATE TABLE pctable

(

id INT NOT NULL AUTO\_INCREMENT,

parent\_id INT,

PRIMARY KEY (id)

) ENGINE=MyISAM;

INSERT INTO pctable (parent\_id) VALUES (0);

INSERT INTO pctable (parent\_id) SELECT parent\_id+1 FROM pctable;

INSERT INTO pctable (parent\_id) SELECT parent\_id+2 FROM pctable;

INSERT INTO pctable (parent\_id) SELECT parent\_id+3 FROM pctable;

INSERT INTO pctable (parent\_id) SELECT parent\_id+4 FROM pctable;

INSERT INTO pctable (parent\_id) SELECT parent\_id+5 FROM pctable;

SELECT \* FROM pctable;

Here is the query to see all Parents, Ancestries, and Family Trees

SELECT

id,parent\_id,

GetParentIDByID(id),

GetAncestry(id),

GetFamilyTree(id)

FROM pctable;

Give it a Try !!!

[Image 1]:

mysql 邻接表,MySQL-邻接表模型-获取深度

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 C++图的建立---邻接矩阵-----邻接表

相关图的邻接表和邻接矩阵

相关 C语言，邻接矩阵，邻接表，十字链表，邻接多重表及其基本操作的实现

相关邻接表与邻接矩阵的对比，邻接表的C语言实现

相关图的邻接矩阵和邻接表表示

相关 mysql 邻接表,MySQL-邻接表模型-获取深度

相关图之邻接表

相关 vector 邻接表

相关邻接表

相关有向图的邻接矩阵、邻接表和逆邻接表