데이터 베이스 MySQL 튜토리얼 Mysql树型结构2种方式及相互转换_MySQL

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

Jun 01, 2016 pm 12:59 PM
방법 구조

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

处理结束;

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

 

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

뜨거운 기사 태그

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

람다 표현식의 구문과 구조적 특징은 무엇입니까? 람다 표현식의 구문과 구조적 특징은 무엇입니까? Apr 25, 2024 pm 01:12 PM

람다 표현식의 구문과 구조적 특징은 무엇입니까?

MySQL.proc 테이블의 구조와 목적에 대한 심층 분석 MySQL.proc 테이블의 구조와 목적에 대한 심층 분석 Mar 15, 2024 pm 02:36 PM

MySQL.proc 테이블의 구조와 목적에 대한 심층 분석

인터넷의 기본 구조와 기술의 근원은 무엇인가? 인터넷의 기본 구조와 기술의 근원은 무엇인가? Dec 15, 2020 pm 04:48 PM

인터넷의 기본 구조와 기술의 근원은 무엇인가?

Go 언어에서 시간 처리 방법은 무엇입니까? Go 언어에서 시간 처리 방법은 무엇입니까? Jun 10, 2023 pm 09:42 PM

Go 언어에서 시간 처리 방법은 무엇입니까?

MySQL에서 쇼핑몰의 평가 테이블 구조를 어떻게 설계하나요? MySQL에서 쇼핑몰의 평가 테이블 구조를 어떻게 설계하나요? Oct 31, 2023 am 08:27 AM

MySQL에서 쇼핑몰의 평가 테이블 구조를 어떻게 설계하나요?

HTML과 CSS를 사용하여 고정된 탐색 메뉴로 레이아웃을 구현하는 방법 HTML과 CSS를 사용하여 고정된 탐색 메뉴로 레이아웃을 구현하는 방법 Oct 26, 2023 am 11:02 AM

HTML과 CSS를 사용하여 고정된 탐색 메뉴로 레이아웃을 구현하는 방법

Linux 파일 시스템의 내부 구조 탐색 Linux 파일 시스템의 내부 구조 탐색 Mar 21, 2024 am 10:03 AM

Linux 파일 시스템의 내부 구조 탐색

Python의 일반적인 흐름 제어 구조는 무엇입니까? Python의 일반적인 흐름 제어 구조는 무엇입니까? Jan 20, 2024 am 10:38 AM

Python의 일반적인 흐름 제어 구조는 무엇입니까?

See all articles