SQL：如何存储树形数据并进行递归遍历（通过查询）？

Question

我想存储一个这样的数据结构。虽然这是个简单的例子，但其他树可能在同一层有多个节点。

（这个树的例子来自 https://github.com/caesar0301/pyTree）

Harry
├── Jane
│   ├── Mark
│   └── Diane
│       ├── Mary
│       └── George
│           └── Jill
└── Bill

我考虑过为每一层创建一个表。

lvl 1 | lvl 2 | lvl 3 | lvl 4  | lvl 5 |
Harry | Jane  | Mark  | Mary   | Jill  |
      | Bill  | Diane | George |       |

我想做一个递归查询或者递归遍历，去访问所有层级的叶子节点。

我应该为每一层创建一个表吗？这听起来不是很好。是不是应该有一个表，里面有一个叫做父节点和子节点的列呢？

id | name  | parent
1  | Harry | 0
2  | Jane  | 1
3  | Bill  | 1
4  | Mark  | 2
5  | Diane | 2
6  | Mary  | 5
7  | Gerge | 5
8  | Jill  | 7

最后，我需要生成一个查询，能够一个接一个地生成以下系列。

Harry, Jane, Mark
Harry, Jane, Diane, Mary
Harry, Jane, Diane, George, Jill (mark Jill as done, because it is a leaf node)
Harry, Jane, Bill

叶子节点在被读取一次后就标记为完成。

额外的节点可以在任何时候、任何层级被添加（由其他进程），我需要一种方法来知道我什么时候“完成”（当所有叶子节点都完成时）。一个包含叶子节点的父节点只有在它所有的子节点都完成时才会被标记为完成。

一些伪代码（我不太确定这个）

getChildren(1)

def getChildren(parent):
  while children.size > 0:
    children = getChildren(parent)
    for child in children:
      if isLeaf(child):
        markDone(child)
      else:
        getChildren(child)

  return children

我需要不时检查一下表，看看是否还有未检查的节点。当没有未检查的节点时，我们就正式“完成”了。

我这样做对吗？还是说有其他更好的解决方案，或者已经有库可以完成这种工作？

Answer 1

在SQL中，有一种有趣的方法可以做到这一点：

http://www.codeproject.com/Articles/8355/Trees-in-SQL-databases

祝你测试顺利。