查询 SQLite 树结构 [英] Querying SQLite Tree structure

问题描述

我有一个这样的表格数据库:

I have a a database of tables like this:

tree{id,name,parent}content{id,content,parent}

tree 表包含一个树状结构，如果 parent 为 0，则它是顶级元素，如果不同，则它是同一表中父元素的 id.

The tree table contains a tree-like structure where if parent is 0 it's the top level element and if it's different, it's the id of the parent from the same table.

content 表有一个 parent 列，它是 tree 表中的一个 id.

The content table has a parentcolumn which is an id from tree table.

我想要的是在给定内容 ID 时获得整个父子元素链.

What I want is to get is the whole chain of parent-children elements when given an ID for content.

我认为这不是表格的最佳结构，我认为我可以改变这一点.

I don't think this is the best structure for the tables and I think I can change this.

请问您对此有何看法?

推荐答案

首先，我建议使用 parent = NULL 而不是零来表示根节点，这将允许 tree 在 parent 上有一个引用 id 的外键；参照完整性很有用.

First of all, I'd recommend using parent = NULL rather than zero to indicate a root node, that would allow tree to have a foreign key on parent which references id; referential integrity is useful.

然后您可以从根节点到每行中的当前节点.物化路径将是一个字符串列，表示从根节点到当前节点的路径；出于您的目的，您希望对路径中的每个节点使用固定宽度格式，然后您可以对路径进行 ASCIIbeically 排序以按树顺序提取记录(如在此 答案).

Then you could include a materialized path from the root node to the current node in each row. The materialized path would be a string column that represents the path from a root node to the current node; for your purposes you'd want to use a fixed-width format for each node in the path, then you could ASCIIbetically sort on the paths to pull records out in tree-order (as in this answer).

假设您认为 99999 足以覆盖您的所有节点.那么你可能有这样的字符串路径:

Suppose you thought 99999 would be enough to cover all your nodes. Then you might have a string path like this:

'00001000110002300042'

这将代表 ID 序列 [1, 11, 23, 42] 所以节点的父节点是 42，祖父节点是 23，依此类推直到 1 的根节点.从节点到根的整个分支:抓取路径，将其拆分为多个部分以获得ID，并在对物化路径进行排序的同时将所有节点拉出以正确的顺序.

That would represent the ID sequence [1, 11, 23, 42] so the node's parent would be 42, the grandparent 23, and so on up to the root of 1. To get the whole branch from a node to the root: grab the path, split it into pieces to get the IDs, and pull out all the nodes at once while sorting on the materialized path to get them out in the right order.

这种方法还可以轻松地一次提取整个子树:只需构建与所需子树匹配的路径前缀，然后执行 path LIKE 'pfx%' ORDER BY path, id 即可提取一次遍历整个子树.此外，大多数数据库将使用以开头的 LIKE 表达式的索引(即 LIKE 'X%' 用于某些 X)，因此这些类型的查询可以很快.您还可以通过简单的字符串长度和除法计算来计算节点的深度.

This approach also makes it easy to extract whole subtrees at once: just build the path prefix that matches your desired subtree and do a path LIKE 'pfx%' ORDER BY path, id to pull out the whole subtree with one pass. Also, most databases will use an index for a LIKE expression that is rooted at the beginning (i.e. LIKE 'X%' for some X) so these sorts of queries can be pretty quick. You can also compute the depth of a node with a simple string length and division computation.

您需要做一些额外的工作来构建物化路径，但不会太多，它们使许多树操作变得简单而简单，同时保持了树的自然表示的优势.

You need to do a little bit of extra work to build the materialized paths but not much and they make a lot of tree operations nice and simple while maintaining the advantages of a natural representation of a tree.

这篇关于查询 SQLite 树结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！