Rumah pangkalan data tutorial mysql Mysql树型结构2种方式及相互转换_MySQL

Mysql树型结构2种方式及相互转换_MySQL

Jun 01, 2016 pm 12:59 PM
Cara struktur

Mysql实现树型结构,数据库上常见有2种方式:领接表、预排序遍历树(MPTT)。
领接表方式——
主要依赖于一个 parent 字段,用于指向上级节点,将相邻的上下级节点连接起来,id 为自动递增自动,parent_id 为上级节点的 id。
领接表方式的优点在于容易理解,代码也比较简单明了。缺点则是递归中的 SQL 查询会导致负载变大,特别是需要处理比较大型的树状结构的时候,查询语句会随着层级的增加而增加,WEB 应用的瓶颈基本都在数据库方面,所以这是一个比较致命的缺点,直接导致树结构的扩展困难重重。
排序遍历树方式
现在我们来聊聊第二种方式─预排序遍历树方式(即通常所说的 MPTT,Modified Preorder Tree Traversal)。此算法是在第一种方式的基础之上,给每个节点增加一个左、右数字,用于标识节点的遍历顺序,如下图所示:

vcq9yrXA/Q==" title="PHP+Mysql树型结构(无限分类)数据库设计的2种方式实例" />

从根节点开始左边为 1,然后下一个节点的左边为 2,以此类推,到最低层节点之后,最低层节点的右边为其左边的数字加 1。顺着这些节点,我们可以很容易地遍历完整个树。根据上图,我们对数据表做一些改变,增加两个字段,lft 和 rgt 用于存储左右数字( left 和 right 是 MySQL 的保留字,所以改用简写)。

可以看出,由于MPTT方式存储不仅包含隶属关系,还包括了顺序,因此在读取子树时不需递归,效率大大提高。

下面面讨论下如何在这两着间转换.

MPTT转领接表比较容易,只要寻找层级比当前节点小1,且lft当前节点rgt的节点,即为父节点。

领接表转MPTT,一般直观想到的是递归生成。但是这个不是尾递归,递归层数有限制, mysql没有数组自建堆栈要用表,效率很低,怎么办?

笔者设计了一个近似递推的算法,分享一下:

首先确定问题:领接表结构(id,pid),目标MPTT表结构(id,lvl,lft,rgt)。

为处理需要,MPTT表增加cnt、seq字段,用于记录节点及其子节点的个数、在MPTT中遍历的序号。

处理过程算法如下:

1】根节点,转入MPTT表,令lvl=1,lft=1,rgt=null,cnt=null,seq=1;

2】逐层处理p的子节点,lvl+1;

3】从最底层(lvl最大)向上(lvl递减)处理各层的节点,cnt=子节点的cnt数+1

4】从最上曾(lvl=1)向下(lvl递增)处理各层的节点,seq=父节点seq+ sum(id小于本节点的兄弟节点的cnt)+1

5】对每一个节点,lft=seq*2-lvl,rgt = lft +cnt *2 -1

处理结束;

此算法已在项目中应用,代码是有版权的,就不贴了。

 

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Tag artikel panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Apakah ciri sintaks dan struktur bagi ungkapan lambda? Apakah ciri sintaks dan struktur bagi ungkapan lambda? Apr 25, 2024 pm 01:12 PM

Apakah ciri sintaks dan struktur bagi ungkapan lambda?

Analisis mendalam tentang struktur dan tujuan jadual MySQL.proc Analisis mendalam tentang struktur dan tujuan jadual MySQL.proc Mar 15, 2024 pm 02:36 PM

Analisis mendalam tentang struktur dan tujuan jadual MySQL.proc

internet的基本结构与技术起源于什么 internet的基本结构与技术起源于什么 Dec 15, 2020 pm 04:48 PM

internet的基本结构与技术起源于什么

Apakah kaedah pemprosesan masa dalam bahasa Go? Apakah kaedah pemprosesan masa dalam bahasa Go? Jun 10, 2023 pm 09:42 PM

Apakah kaedah pemprosesan masa dalam bahasa Go?

Bagaimana untuk mereka bentuk struktur jadual penilaian pusat membeli-belah dalam MySQL? Bagaimana untuk mereka bentuk struktur jadual penilaian pusat membeli-belah dalam MySQL? Oct 31, 2023 am 08:27 AM

Bagaimana untuk mereka bentuk struktur jadual penilaian pusat membeli-belah dalam MySQL?

Cara melaksanakan susun atur dengan menu navigasi tetap menggunakan HTML dan CSS Cara melaksanakan susun atur dengan menu navigasi tetap menggunakan HTML dan CSS Oct 26, 2023 am 11:02 AM

Cara melaksanakan susun atur dengan menu navigasi tetap menggunakan HTML dan CSS

Meneroka struktur dalaman sistem fail Linux Meneroka struktur dalaman sistem fail Linux Mar 21, 2024 am 10:03 AM

Meneroka struktur dalaman sistem fail Linux

Apakah struktur kawalan aliran biasa dalam Python? Apakah struktur kawalan aliran biasa dalam Python? Jan 20, 2024 am 10:38 AM

Apakah struktur kawalan aliran biasa dalam Python?

See all articles