MySQL 所推荐的上下值法(毗邻目录法、预排序历遍法)
MySQL 所推荐的左右值法(毗邻目录法、预排序历遍法)毗邻目录法:这种方法说白了就是子类,依赖父类,父类依赖
MySQL 所推荐的左右值法(毗邻目录法、预排序历遍法)
毗邻目录法:
这种方法说白了就是子类,依赖父类,父类依赖爷爷类,爷爷类可以有多个儿子类,跟父类平级的类。一层一层的。
预排序历遍法:
这种算法比较高端,使用的是mysql官方推荐的左右算法。
使用场合:多级目录,多层关联的情况。
而我的使用场合就是典型的省市县3级关联。下面先来简单了解下它们的原理。
关于省市县的文章以后有空再放出。
以下3篇文章分别摘自互联网。都是3位前辈的分析,可以学习之。
一、引言
产品分类,多级的树状结构的论坛,邮件列表等许多地方我们都会遇到这样的问题:如何存储多级结构的数据?在PHP的应用中,提供后台数据存储的通常是关系型数据库,它能够保存大量的数据,提供高效的数据检索和更新服务。然而关系型数据的基本形式是纵横交错的表,是一个平面的结构,如果要将多级树状结构存储在关系型数据库里就需要进行合理的翻译工作。接下来我会将自己的所见所闻和一些实用的经验和大家探讨一下:
层级结构的数据保存在平面的数据库中基本上有两种常用设计方法:
毗邻目录模式(adjacency list model)预排序遍历树算法(modified preorder tree traversal algorithm)
我不是计算机专业的,也没有学过什么数据结构的东西,所以这两个名字都是我自己按照字面的意思翻的,如果说错了还请多多指教。这两个东西听着好像很吓人,其实非常容易理解。
二、模型
这里我用一个简单食品目录作为我们的示例数据。
我们的数据结构是这样的,以下是代码:
相关创建数据语句:
CREATE TABLE category(
category_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
parent INT DEFAULT NULL);
INSERT INTO category
VALUES(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);
SELECT * FROM category ORDER BY category_id;
在这种数据结构中,各层之间通过字段 parent 来形成邻接表,我们查询某些层级的关系的时候一般都是通过递归的方式,遍历某个层级关系的SQL的查询次数会顺着层级的增加,想想在层级有20的时候,根据某个底层节点取它到顶层节点的查询次数吧。
为了解决这个问题,人们想出了嵌套集模型(The Nested Set Model),请看下图:
上图依然是表现的与图一相同的层级关系,但是却更换了一种表现形式 下面是新的关系表和数据(关系和数据与之前相同,但是表结构不一样):
CREATE TABLE nested_category (
category_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
lft INT NOT NULL,
rgt INT NOT NULL
);
INSERT INTO nested_category
VALUES(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);
SELECT * FROM nested_category ORDER BY category_id;
这里将 left,right 修改为 lft,rgt因为这两个词在MYSQL中属于关键字 下面我们将插入的数据标识在图上:
同样,我们将数据标识在原来的结构上:
怎么样,是不是很明确了
下面使我自己标定一种形式,方便理解
[1
[2
[3 4]
[5 6]
[7 8]
9]
[10
[11
[12 13]
14]
[15 16]
[17 18]
19]
20]
===========================================================
以上是MySQL 所推荐的左右值法(毗邻目录法、预排序历遍法)
我的想法是根据category的内容,用一个存储过程来计算,把结果算出来放到nested_category中。