下载文档原格式
树形结构的数据库表Schema设计程序设计过程中，我们常常用树形结构来表征某些数据的关联关系，如企业上下级部门、栏目结构、商品分类等等，通常而言，这些树状结构需要借助于数据库完成持久化。
然而目前的各种基于关系的数据库，都是以二维表的形式记录存储数据信息，因此是不能直接将Tree存入DBMS，设计合适的Schema及其对应的CRUD算法是实现关系型数据库中存储树形结构的关键。
理想中树形结构应该具备如下特征：数据存储冗余度小、直观性强；检索遍历过程简单高效；节点增删改查CRUD 操作高效。
无意中在网上搜索到一种很巧妙的设计，原文是英文，看过后感觉有点意思，于是便整理了一下。
本文将介绍两种树形结构的Schema设计方案：一种是直观而简单的设计思路，另一种是基于左右值编码的改进方案。
一、基本数据本文列举了一个食品族谱的例子进行讲解，通过类别、颜色和品种组织食品，树形结构图如下：二、继承关系驱动的Schema设计对树形结构最直观的分析莫过于节点之间的继承关系上，通过显示地描述某一节点的父节点，从而能够建立二维的关系表，则这种方案的Tree表结构通常设计为：{Node_id,Parent_id}，上述数据可以描述为如下图所示：这种方案的优点很明显：设计和实现自然而然，非常直观和方便。
缺点当然也是非常的突出：由于直接地记录了节点之间的继承关系，因此对Tree的任何CRUD操作都将是低效的，这主要归根于频繁的“递归”操作，递归过程不断地访问数据库，每次数据库IO都会有时间开销。
当然，这种方案并非没有用武之地，在Tree规模相对较小的情况下，我们可以借助于缓存机制来做优化，将Tree的信息载入内存进行处理，避免直接对数据库IO操作的性能开销。
三、基于左右值编码的Schema设计在基于数据库的一般应用中，查询的需求总要大于删除和修改。
为了避免对于树形结构查询时的“递归”过程，基于Tree的前序遍历设计一种全新的无递归查询、无限分组的左右值编码方案，来保存该树的数据。
树状的总结1. 引言在计算机科学和信息管理领域中，树状结构（Tree）是一种常见且重要的数据结构。
树的结构类似于现实生活中的树，具有分支和节点的层级关系。
树状结构具有广泛的应用，例如数据库索引、文件系统、网络路由等。
本文将对树的概念、特点以及常见的应用进行总结和介绍。
2. 树的基本概念树是由节点（Node）和边（Edge）组成的一种非线性数据结构。
树中有一个特殊的节点称为根节点（Root），根节点没有父节点，其他节点都有一个父节点。
在一个树中，每个节点都可以有零个或多个子节点，节点之间通过边连接。
树状结构的特点包括： - 根节点：树的入口，唯一的起点。
- 父节点：每个节点都有一个父节点，除了根节点。
- 子节点：父节点下的节点称为子节点。
- 叶子节点：没有子节点的节点称为叶子节点。
- 节点间的关系：节点之间通过边连接，形成层级结构。
树可以用图形表示，例如下面这个简单的示例树：A/ \\B C/ \\ / \\D E F G在这个示例中，根节点是A，它有两个子节点B和C。
B节点有两个子节点D和E，C节点有两个子节点F和G。
节点D、E、F、G都是叶子节点，它们没有子节点。
3. 树的常见应用树状结构在计算机科学和信息管理领域中有广泛的应用，以下是一些常见的应用示例：3.1 数据库索引在数据库中，树状结构被广泛应用于索引。
数据库使用树状结构来加速数据的检索和查询操作。
常见的数据库索引结构包括B树（B-Tree）、B+树（B+ Tree）、红黑树（Red-Black Tree）等。
通过使用树索引，数据库可以快速定位和访问数据，提高查询效率。
3.2 文件系统文件系统通常使用树状结构来组织和管理文件和目录。
树的根节点代表文件系统的根目录（例如：C:\）。
每个子目录都是一个节点，子目录之间通过边连接。
通过树的结构，文件系统可以方便地浏览和管理文件和目录。
常见的文件系统包括Windows中的NTFS、Linux中的EXT4等。
数据结构树的种类树是一种基本的数据结构，用于表示具有层次结构的数据。
它由一组节点组成，其中的每个节点都可以有零个或多个子节点。
树可以有不同的种类，每种种类具有不同的特点和应用场景。
以下是一些常见的树的种类：1. 二叉树（Binary Tree）：二叉树是一种每个节点最多只有两个子节点的树结构。
它可以是空树，或者由一个根节点、左子树和右子树组成。
二叉树具有简单的结构，常用于二分和排序。
2. 二叉树（Binary Search Tree）：二叉树是一种具有以下特点的二叉树：左子树中的所有节点都比根节点小，右子树中的所有节点都比根节点大。
二叉树支持快速的查找、插入和删除操作，并在树中保持有序性。
3. 平衡二叉树（Balanced Binary Tree）：平衡二叉树是一种二叉树，但它在插入和删除节点时会自动调整树的结构以保持树的平衡性。
平衡二叉树的常见实现包括 AVL 树和红黑树，它们可以提供在最坏情况下仍保持对数时间复杂度的查找、插入和删除操作。
4. B树（B-Tree）：B树是一种自平衡的树结构，它具有以下特点：每个节点可以有多个子节点，每个节点中的键值有序排列，并且每个节点中的键值数量有一个上限和下限。
B树通常用于大规模数据的存储和数据库系统。
5. Trie树（Trie Tree）：Trie树，也称为字典树或前缀树，是一种专门用于处理字符串集合的树结构。
Trie树的每个节点都代表一个字符串前缀，通过将字符逐级插入树中，可以高效地完成字符串的和查找操作。
6. 线段树（Segment Tree）：线段树是一种用于处理区间查询问题的树结构。
它将要处理的区间划分为一系列离散的线段，并为每个线段创建一个节点。
线段树可以高效地回答关于区间的统计性质，如区间最小值、区间最大值、区间和等。
7. 堆（Heap）：堆是一种完全二叉树，它具有以下特点：对于每个节点，它的值都大于等于（或小于等于）它的子节点的值。
堆被广泛应用于优先队列、排序算法（如堆排序）以及图算法中。
oid为典型的树形编码结构-回复什么是典型的树形编码结构？树形编码结构是一种数据组织方式，它通过将数据按照树的结构进行编码，使得数据在存储和检索时更加高效。
典型的树形编码结构是指使用树形结构来表示一种普遍应用的编码方式。
在典型的树形编码结构中，数据被组织成一个有层次关系的树形结构。
树形结构由节点和边组成，树的顶部被称为根节点，根节点下面连接着多个子节点，子节点之间可以再连接其他子节点，形成一个分支。
树形结构的末端节点被称为叶子节点，它们处于树的最底层，不再连接其他节点。
树形编码结构常用于存储和管理层级化的数据，比如文件系统、目录结构、组织架构等。
下面将以文件系统为例，一步一步回答什么是典型的树形编码结构。
一、树的根节点：在文件系统中，根节点代表整个文件系统的起点，它没有父节点，是树的顶层。
在操作系统中，通常使用一个特殊的符号（例如“/”）作为根节点的表示。
二、子节点和叶子节点：对于文件系统来说，子节点代表文件夹，叶子节点代表文件。
一个文件夹可以包含多个子文件夹和文件，而文件没有子节点。
子节点和叶子节点之间通过边连接起来，表示它们之间的层次关系。
三、层级关系：文件系统中的文件夹可以以层级关系组织起来，形成一个多级目录结构。
每个文件夹可以包含其他文件夹和文件，这些文件夹和文件可以再次包含其他文件夹和文件，从而形成了一个层级化的树形结构。
四、路径：路径表示了从根节点到达某个节点的唯一路线。
在文件系统中，路径通常由根节点的表示和一系列文件夹的名称组成，使用特定的分隔符（例如“/”）进行分隔。
通过路径，可以精确定位到特定的文件或文件夹，实现对其进行访问和操作。
五、遍历：树形编码结构的一个重要操作是遍历，即按照一定的顺序访问树中的所有节点。
在文件系统中，常见的遍历方式有深度优先遍历和广度优先遍历。
深度优先遍历按照从根节点开始，先递归遍历子节点，再回溯到父节点，再遍历其他子节点的顺序进行。
广度优先遍历则按照层级顺序，从根节点开始逐层遍历。
数据结构树的应用数据结构树的应用数据结构是计算机科学中重要的一个分支，而树是其中一种重要且实用的数据结构之一。
树是由一个根节点和若干子节点组成的一种非线性数据结构，被广泛应用于计算机领域中，特别是在算法设计和数据处理方面。
下面我们将详细介绍树的应用领域。
1. 数据库在数据库管理系统中，树被广泛应用于索引结构。
数据库中的查找过程可以转化为在树中查找某个节点的过程。
常用的树结构包括B-树、B+树和红黑树，这些结构可以高效的处理大量数据，支持高效的检索和排序。
2. 文件系统操作系统中的文件系统其实就是一种树形结构。
目录和文件被视为节点，而目录之间的关系和文件之间的关系则是树的关系。
基于树形结构的文件系统使得我们可以很方便地在系统中查找和管理文件。
3. 编程语言树形结构被广泛运用于编程语言中。
AST（抽象语法树）就是一种常见的语法分析树，它将程序中的语句和表达式抽象成一个树形结构，在编译器中被广泛使用，可以很方便地实现代码的词法分析、语义分析和优化。
此外，树也可以用于构建运行时数据结构，如二叉搜索树、Trie树、AVL树等等。
4. 网络在计算机网络中，树的结构被广泛应用于路由器和交换机中。
这些设备需要通过识别和分析网络中的数据包，将它们分配到不同的路由或交换机上进行处理。
树的结构使得这些设备可以很方便地对不同的数据包进行分类、处理和转发。
5. 人工智能在人工智能中，树也是非常重要的一种数据结构。
决策树是常用的机器学习算法之一，它通过一系列的二叉树形结构对数据进行分类和判断。
在处理自然语言、语音识别和图像处理等领域中，树结构也被广泛应用。
总之，数据结构树在计算机领域中有着非常广泛的应用，可以用于解决各种问题。
从数据库、文件系统到编程语言、网络和人工智能等领域，都需要树这种数据结构来达到高效、快速、准确处理数据的目的。
因此，学习并掌握树这种数据结构非常重要，可以帮助我们更好地理解计算机领域内的各种问题和算法。
树形数据结构及其特点树形数据结构是计算机科学中一种重要的数据结构，它模拟了现实世界中的树的结构，具有分层的特点。
树形数据结构由节点（node）和边（edge）组成，节点之间通过边相连，形成了层次关系。
在树形数据结构中，有一个特殊的节点被称为根节点（root），它位于树的顶部，其他节点则根据其在树中的位置被分为父节点（parent node）和子节点（child node）。
树形数据结构具有许多重要的特点，下面将逐一介绍。
1. **层次性**：树形数据结构是一种层次性的结构，节点之间存在明确的层次关系。
根节点位于最顶层，其下可以有多个子节点，每个子节点又可以有自己的子节点，以此类推，形成了层层递进的结构。
2. **唯一性**：在树形数据结构中，每个节点都有且仅有一个父节点（除了根节点），但可以有多个子节点。
这种唯一性的特点保证了树的结构清晰明了，不会出现歧义。
3. **无环性**：树形数据结构是一种无环的结构，即不存在环路。
在树中沿着任意路径都不会回到同一个节点，这样可以避免数据访问时的死循环问题。
4. **递归性**：树形数据结构具有递归性质，即树本身可以看作是由多个子树组成的。
每个子树又可以继续分解为更小的子树，这种递归结构方便对树进行遍历和操作。
5. **高效性**：树形数据结构在查找、插入和删除等操作上具有高效性。
由于树的层次性和唯一性，可以通过递归或迭代的方式快速定位到目标节点，而不需要遍历整个数据集。
6. **灵活性**：树形数据结构非常灵活，可以根据实际需求进行扩展和定制。
例如，可以衍生出二叉树、平衡树、B树等不同类型的树结构，以满足不同场景下的数据存储和检索需求。
总的来说，树形数据结构是一种非常重要且实用的数据结构，广泛应用于计算机科学领域的各个方面，如数据库索引、文件系统、编译器等。
熟练掌握树形数据结构及其特点对于提高程序设计的效率和质量具有重要意义。
希望本文对读者对树形数据结构有更深入的了解和认识。
树形结构数据库表设计转载：逻辑数据库设计 - 单纯的树(递归关系数据)相信有过开发经验的朋友都曾碰到过这样⼀个需求。
假设你正在为⼀个新闻⽹站开发⼀个评论功能，读者可以评论原⽂甚⾄相互回复。
这个需求并不简单，相互回复会导致⽆限多的分⽀，⽆限多的祖先-后代关系。
这是⼀种典型的递归关系数据。
对于这个问题，以下给出⼏个解决⽅案，各位客观可斟酌后选择。
⼀、邻接表:依赖⽗节点 邻接表的⽅案如下(仅仅说明问题)： CREATE TABLE Comments( CommentId int PK, ParentId int, --记录⽗节点 ArticleId int, CommentBody nvarchar(500), FOREIGN KEY (ParentId) REFERENCES Comments(CommentId) --⾃连接，主键外键都在⾃⼰表内 FOREIGN KEY (ArticleId) REFERENCES Articles(ArticleId) ) 由于偷懒，所以采⽤了书本中的图了，Bugs就是Articles： 这种设计⽅式就叫做邻接表。
这可能是存储分层结构数据中最普通的⽅案了。
下⾯给出⼀些数据来显⽰⼀下评论表中的分层结构数据。
⽰例表： 图⽚说明存储结构：邻接表的优缺分析 邻接表的优缺分析 对于以上邻接表，很多程序员已经将其当成默认的解决⽅案了，但即便是这样，但它在从前还是有存在的问题的。
分析1：查询⼀个节点的所有后代(求⼦树)怎么查呢？ 我们先看看以前查询两层的数据的SQL语句： SELECT c1.*,c2.* FROM Comments c1 LEFT OUTER JOIN Comments2 c2 ON c2.ParentId = mentId 显然，每需要查多⼀层，就需要联结多⼀次表。
SQL查询的联结次数是有限的，因此不能⽆限深的获取所有的后代。
⽽且，这种这样联结，执⾏Count()这样的聚合函数也相当困难。
obbtree 原理obbtree是一种用于高效存储和查询大量有序数据的数据结构。
其原理基于最优双调分裂（Optimal Bi-Partitions）和最优倍增分割（Optimal Doubling Splits）。
obbtree将有序数据划分为多个块，并通过基于索引的方式加速搜索和查询。
每个块由一组连续的数据项构成，其中第一个数据项是分隔符，用于确定块的边界。
obbtree按照特定规则选择分隔符，通常是选择划分区间中的中位数作为分隔符。
obbtree中的每个块都有一个“块宽度”（block width），表示该块中包含的数据项的数量。
这个块宽度可以是固定的，也可以根据数据的分布情况进行动态调整。
根据块宽度，obbtree可以高效地定位需要查询的数据项所在的块。
在obbtree中，块的选择以及查询的方式与最优双调分裂和最优倍增分割有关。
最优双调分裂是通过选择最佳的分割点将数据集一分为二，使得分割点的左边的数据项数尽量接近右边的数量。
最优倍增分割则是在已有的块中选择最佳的分割点进行“插入式”分割，以保持数据的有序性。
这两种分割策略能够保证obbtree的查询效率较高。
在obbtree中，数据的插入和删除操作也是通过最优双调分裂和最优倍增分割来实现的。
当需要插入新的数据项时，obbtree 会寻找最合适的块进行分割，保持数据的有序性。
同样，当需要删除数据项时，obbtree也会通过合并块的方式来调整数据的分布情况。
总的来说，obbtree通过使用最优双调分裂和最优倍增分割来维护有序数据的分布，通过索引方式加速查询和查找操作，从而实现了高效的存储和查询大量有序数据的功能。
采用左右值编码来存储无限分级树形结构的数据库表设计之前我介绍过一种按位数编码保存树形结构数据的表设计方法，详情见：浅谈数据库设计技巧(上)该设计方案的优点是：只用一条查询语句即可得到某个根节点及其所有子孙节点的先序遍历。
由于消除了递归，在数据记录量较大时，可以大大提高列表效率。
但是，这种编码方案由于层信息位数的限制，限制了每层能所允许的最大子节点数量及最大层数。
同时，在添加新节点的时候必须先计算新节点的位置是否超过最大限制。
上面的设计方案必须预先设定类别树的最大层数以及最大子节点数，不是无限分级，在某些场合并不能采用，那么还有更完美的解决方案吗？通过google的搜索，我又探索到一种全新的无递归查询，无限分级的编码方案——左右值。
原文的程序代码是用php写的，但是通过仔细阅读其数据库表设计说明及相关的sql语句，我彻底弄懂了这种巧妙的设计思路，并在这种设计中新增了删除节点，同层平移的需求（原文只提供了列表及插入子节点的sql语句）。
下面我力图用比较简短的文字，少量图表，及相关核心sql语句来描述这种设计方案：首先，我们弄一棵树作为例子：商品|---食品| |---肉类| | |--猪肉| |---蔬菜类| |--白菜|---电器|--电视机|--电冰箱select count(*) from tree where lft <= 2 and rgt >= 11为了方便列表，我们可以为tree表建立一个视图，添加一个层数列，该类别的层数可以写一个自定义函数来计算。
该函数如下：CREATE FUNCTION dbo.CountLayer(@type_id int)RETURNS intASbegindeclare@result intset@result=0declare@lft intdeclare@rgt intif exists (select1from tree where type_id=@type_id)beginselect@lft=lft,@rgt=rgt from tree where type_id=@type_idselect@result=count(*) from tree where lft <=@lft and rgt >=@rgtendreturn@resultendGO然后，我们建立如下视图：CREATE VIEW dbo.TreeViewASSELECT type_id, name, lft, rgt, dbo.CountLayer(type_id) AS layer FROM dbo.tree ORDE R BY lftGO()AS declare declare ifgo假定我们要在节点“肉类”下添加一个子节点“牛肉”，该树将变成：1商品18+2+--------------------------------------------+2食品11+2 12+2电器17+2+-----------------+ +-------------------------+3肉类6+2 7+2蔬菜类10+2 13+2电视机14+2 15+2电冰箱16+2 +-------------+4猪肉5 6牛肉78+2白菜9+2看完上图相应节点左右值的变化后，相信大家都知道该如何写相应的sql脚本吧？下面我给出相对完整的插入子节点的存储过程：CREATE PROCEDURE[dbo].[AddSubNodeByNode](@type_id int,@name varchar(50))ASdeclare@rgt intif exists (select1from tree where type_id=@type_id)beginSET XACT_ABORT ONBEGIN TRANSACTIONselect@rgt=rgt from tree where type_id=@type_idupdate tree set rgt=rgt+2where rgt>=@rgtupdate tree set lft=lft+2where lft>=@rgtinsert into tree (name,lft,rgt) values (@name,@rgt,@rgt+1)COMMIT TRANSACTIONSET XACT_ABORT OFFend然后，我们删除节点“电视机”，再来看看该树会变成什么情况：1商品20-2+-----------------------------------+2食品13 14电器19-2+-----------------+3肉类8 9蔬菜类12 17-2电冰箱18-2+----------+4猪肉5 6牛肉7 10白菜11相应的存储过程如下：CREATE PROCEDURE[dbo].[DelNode]@type_id intASdeclare@lft intdeclare@rgt intif exists (select1from tree where type_id=@type_id)beginSET XACT_ABORT ONBEGIN TRANSACTIONselect@lft=lft,@rgt=rgt from tree where type_id=@type_iddelete from tree where lft>=@lft and rgt<=@rgtupdate tree set lft=lft-(@rgt-@lft+1) where lft>@lftupdate tree set rgt=rgt-(@rgt-@lft+1) where rgt>@rgtCOMMIT TRANSACTIONSET XACT_ABORT OFFEnd注意：因为删除某个节点会同时删除该节点的所有子孙节点，而这些被删除的节点的个数为：(被删节点的右值-被删节点的左值+1)/2，而任何一个节点同时具有唯一的左值和唯一的右值，故删除作废节点后，其他相应节点的左、右值需要调整的幅度应为：减少(被删节点的右值-被删节点的左值+1)。
最后，让我们看看平移节点“电器”，将其和其所有子孙节点移动到节点“食品”之前后，该树会变成什么情况：1商品18+-----------------------------------+14-12电器17-12 2+4食品13+4+----------------------+ 15-12电冰箱16-12 3+4肉类8+4 9+4蔬菜类12+4+-------------------+4+4猪肉5+4 6+4牛肉7+4 10+4白菜11+4大家仔细观察一下交换后同层2个节点和其所有子孙节点左右值的变化，可以发现一个明显的规律，那就是，节点“电器”及其所有子孙节点的左右值均减少12，而节点“食品”及其所有子孙节点的左右值均增加4。
而节点“电器”+其子孙节点的数量为2，节点“食品”+其子孙节点的数量为6，这其中有什么联系吗？还记得我在删除节点的存储过程后面的注释吗？任何一个节点同时具有唯一的左值和唯一的右值。
让我们把节点数量*2，正好和节点左右值需要调整的幅度相等。
由此规律，我们可以编写出类似下面的存储过程来实现节点同层前移的功能：CREATE PROCEDURE[dbo].[MoveNodeUp]@type_id intASdeclare@lft intdeclare@rgt intdeclare@layer intif exists (select1from tree where type_id=@type_id)beginSET XACT_ABORT ONBEGIN TRANSACTIONselect@lft=lft,@rgt=rgt,@layer=layer from TreeView where type_id=@type_idif exists (select*from TreeView where rgt=@lft-1and layer=@layer)begindeclare@brother_lft intdeclare@brother_rgt intselect@brother_lft=lft,@brother_rgt=rgt from TreeView where rgt=@lft-1an d layer=@layerupdate tree set lft=lft-(@brother_rgt-@brother_lft+1) where lft>=@lft and rgt <=@rgtupdate tree set lft=lft+(@rgt-@lft+1) where lft>=@brother_lft and rgt<=@br other_rgtupdate tree set rgt=rgt-(@brother_rgt-@brother_lft+1) where rgt>@brother_ rgt and rgt<=@rgtupdate tree set rgt=rgt+(@rgt-@lft+1) where lft>=@brother_lft+(@rgt-@lft+ 1) and rgt<=@brother_rgtendCOMMIT TRANSACTIONSET XACT_ABORT OFFend注意：节点的同层平移可以采用临时表来做中介，降低代码的复杂度。
不用临时表来处理也行，但是update语句顺序一定要考虑周详。
否则，一旦出现bug，对整个类别表的破坏是惊人的，强烈推荐在做上述工作前对类别表进行完整备份。
同层下移的存储过程和同层上移类似，有兴趣的朋友可以自己动手编写体味一下其中的细节，我就不在这里列出来了。
最后，我对上面这种左右值编码实现无限分级类别树的方案做一个总结：优点：在消除递归的前提下实现了无限分级，而且查询条件是基于整形数字比较的，效率很高。
可以进行先序列表，添加，修改，删除，同层平移等常规操作，基本满足需求。
缺点：由于这种左右值编码的方式和常见的阿拉伯数字直观排序不同，再加上节点在树中的层次，顺序不是直观显示出来，而必须通过简单的公式计算后得到，需要花费一定的时间对其数学模型进行深入理解。
而且，采用该方案编写相关存储过程，新增，删除，同层平移节点需要对整个树进行查询修改，由此导致的代码复杂度，耦合度较高，修改维护的风险较高。
发表于@ 2007年04月26日16:36:00|评论(4 )|编辑新一篇: 自定义MembershipProvider来利用 2.0 Login控件的登陆和修改密码模块 | 旧一篇: 分页存储过程的一点心得老板心里你有多重？确立职场位置，明确自身重要性Leo教你看清前途老板心里你有多重？确立职场位置，明确自身重要性Leo教你看清前途评论#hometohome 发表于2008-05-07 22:17:19 IP: 123.115.4.*请问该如何根据子节点的type_id找出父节点呢？比如：猪肉的父节点是肉类、食品、商品#hometohome 发表于2008-05-07 22:38:54 IP: 123.115.4.*declare @rgt intselect @rgt=rgt from tree where type_id=13select * from tree where rgt>=@rgt and lft<=@rgt order by lft我是楼上的。
