Clever Geek Handbook

在.Net条件下增长嵌套集





嗨，我叫Anton，我是一名开发人员。儿子我生了，房子建买了，但它仍然长出了树。由于我不是农艺师，所以我不得不编码一棵树。我们的项目由.Net Core上的多个微服务组成，形成分层关系的实体存储在PostgreSQL数据库中。我将告诉您最好选择哪种结构来存储此类数据，为什么要使用精确的嵌套集，可以踩哪些耙子以及以后如何使用它。



什么是嵌套集



每个人都知道树如何在花园中生长，对于嵌套集，树的生长方式如下：对于每个节点，存储的两个字段Left和Right都是整数。这里的逻辑是Left小于Right，如果一个节点有子节点，那么所有子节点的Left和Right值都必须在父节点的相应值之间。





他们如何与我们一起成长



我们专门提供了一个单独的微服务来存储层次结构。Fronted通常必须在详细视图中绘制元素的完整树以及子树，而插入和移动元素相对较少。对于这种情况，嵌套集是完美的。存储在这样的表中：





id是相应实体的标识符，使用它您可以从适当的微服务获取完整的信息。TreeId是根元素的标识符。该项目中的树木大多很小，但其中很多。EntityFramework用于从数据库读取，该类与表结构一对一对应。



如何阅读



使用这种存储方法，获得子树的元素很简单-我们请求所有Left大于父级Left的节点，Right小于其父级的节点。我们还通过TreeId列检查所有节点都属于同一棵树。这是最常需要的操作，可以快速执行。例如，像这样： 



dataContext.Nodes.Where(_ => 
                        _.Left > node.Left && 
                        _.Right < node.Right && 
                        _.TreeId == node.TreeId);


另一个经常执行的操作是查找对象的所有父节点。在这里，也不难-我们请求的树节点的Left小于父元素的Left，而Right相应地更大。例如，以这种方式： 



dataContext.Nodes.Where(_ => 
                        _.Left < node.Left && 
                        _.Right > node.Right && 
                        _.TreeId == node.TreeId);


如何发展新的分支机构



让我们继续进行困难的部分-移植，即 添加节点或从一个子树移动到另一个子树。让我们弄清楚如何进行转移，因为 此操作实质上包括添加子元素所需的一切。



成功插入的第一件事是仅允许一个插入或更新操作。为此，我们将使用阻塞。锁定整个表没有任何意义，因为节点只能在一棵树内导航，因此仅锁定该树就足够了。为此，请执行以下SQL查询： 



select * from "Nodes" where "TreeId" = <TreeId> for update;


这将使我们能够立即读取树的元素，但是如果我们需要在树中添加或更改已经开始这种操作的节点，则我们将不得不等待上一个操作完成。



下一步是为移植做准备-在左右之间留出空隙。让我们计算需要多少空间-这是要移动的子树的根元素的“右”和“左”之间的差。将此差异添加到将成为新父节点的节点的所有子节点上。我们可以在这里捕获Exception，这就是原因。为了加快表中的搜索和读取速度，在Left和Right字段上添加了两个B-Tree索引，如果同时更改这些字段的值，则EntityFramework可能会给出循环依赖错误，因为可以同时在一行上重新计算两个索引。该错误的类型为InvalidOperationException，并显示以下消息：



由于在要保存的数据中检测到循环依赖性，因此无法保存更改：'节点[已修改] <-索引{'右'，'TreeId'}节点[已修改] <-索引{'左'，'TreeId'}节点[修改]'。


为了解决这个问题，我们将仅进行两个单独的循环-在一个循环中，我们将更改Left，在另一个循环中，当然，我们将在每个循环之后保存更改。 




            var nodesToMove = await dataContext.Nodes 
                .Where(n => 
                    n.Right >= parentNodeRight && 
                    n.TreeId == parentNode.TreeId) 
                .OrderByDescending(n => n.Right) 
                .ToListAsync(); 
 
            foreach (var n in nodesToMove) 
            { 
                n.Left += distance; 
            } 
 
            await dataContext.SaveChangesAsync(); 
 
            foreach (var n in nodesToMove) 
            { 
                n.Right += distance; 
            } 
 
            await dataContext.SaveChangesAsync();


此外，移植本身-传输距离将等于新父对象的Left与子树的根的Left之间的差。将此值添加到要移动的子树中所有节点的“左”和“右”。 




            var nodes = await dataContext.Nodes 
                .Where(n => 
                    n.Left >= node.Left && 
                    n.Right <= node.Right && 
                    n.TreeId == node.TreeId) 
                .ToListAsync(); 
 
            foreach (var n in nodes) 
            { 
                n.Left += distance; 
                n.Right += distance;


最后要做的是关闭子树移动的间隙。让我们请求此子树右边的所有节点-这些元素将是其Right大于或等于子树根的Left的元素，然后将它们移到空闲空间。为此，请从所有这些节点的“左”和“右”减去根的“右”和“左”之间的差。在这里，您也必须执行两个单独的循环： 




            var nodesToMove = await dataContext.Nodes 
              .Where(n => n.Right >= gap.Left && n.TreeId == gap.TreeId) 
              .ToListAsync(); 
            nodesToMove = nodesToMove 
                .Where(n => n.Right >= gap.Right) 
                .OrderBy(n => n.Right) 
                .ToList(); 
 
            foreach (var n in nodesToMove) 
            { 
                if (n.Left >= gap.Right) 
                { 
                    n.Left -= distance; 
                } 
            } 
 
            await dataContext.SaveChangesAsync(); 
 
            foreach (var n in nodesToMove) 
            { 
                n.Right -= distance; 
            } 
 
            await dataContext.SaveChangesAsync();


结论



让我们看看增长了。我们有一棵能快速阅读孩子和父母的树。如果您的项目需要经常读取数据并检索子树，则嵌套集是一个不错的选择。我们必须为插入和更新操作可能存在问题这一事实做好准备，但这些问题可以解决。如果您必须频繁添加和传输，最好考虑使用其他算法，或者考虑使用一些混合选项。例如，交叉嵌套集和邻接列表。为此，在每个节点中，除了“左”和“右”，还需要添加直接链接到父元素标识符。这将使您能够快速导航层次结构并找到父节点和子节点，此外，还将提高算法的可靠性。


More articles:


All Articles