Quote:
|
Originally Posted by sql_wtf?
Well, I'm not sure about my intelligence or b+tree (yes, the variant of b-tree) anymore  . Are you familiar with the concept of two-pane outliner? I need almost the same thing.
I have a left pane of window in wich I have a tree-view control, user can add/delete/rename child nodes, chiled nodes can have any[my emphasis] number of child nodes, which can have .... To the every node user can add/delete some data. |
So you want something that looks like folder view in Windows explorer.
But if you want
any number of child nodes, you're not dealing with a binary tree. It's just a tree.
Let me point out that you probably shouldn't implement an arbitrarily nested tree. It's a terrible way to do a GUI. When was the last time you dug into a Windows help file to find something? Or tediously searched through folders? I haven't done it ever since Spotlight came out on the Mac and Google Desktop came out for Windows.
I haven't seen proper research on it, but from experience I'd say that the user shouldn't be exposed to more than 5 levels of nesting.
And if you take my advice, you don't need a tree in SQL. You can just have fields like cat1, cat2, cat3, cat4.
But if you're dead set on an infinitely expandable tree... Here's one way of declaring a tree in SQL:
Code:
CREATE TABLE nodes (
id INTEGER PRIMARY KEY,
parent INTEGER NOT NULL REFERENCES nodes(id)
CHECK((id = 0 AND parent = 0) OR (id <> 0 and id <> parent)),
payload SOME_TYPE,
payload2 SOME_TYPE,
...
)
id is a number for the node. Since it uniquely identifies the node, it's the primary key. You can have other candidate keys, if necessary.
I arbitrarily picked 0 to be the "root" node.
parent identifies the node directly above this node, except for the root node which simply links back to itself. To make this work, parent has three constraints.
1. It can't be null. Every node has to have a parent.
2. It has to refer to a real node. The "REFERENCES" clause is shorthand for declaring a foreign key constraint. In this case, it's a self-referential constraint.
3. One of these two statements are true: this is the root node and parent refers to itself, *or* it's not the root node and its parent is some other node.
This is a start but it's not a perfect implementation. You could still create a circular system like this:
Code:
INSERT INTO nodes VALUES (0, 0)
INSERT INTO nodes VALUES (1, 0)
INSERT INTO nodes VALUES (2, 1)
INSERT INTO nodes VALUES (3, 2)
UPDATE nodes SET parent = 3 WHERE id = 1
There are different ways to fix this, depending on what functionality you need.
Actually working with the tree is pretty easy because the DBMS takes care of allocation and deallocation. It helps to learn how to write stored procedures and triggered procedures.
dBforums
>
b+tree and the SQLite
03-16-07, 13:20
Linear Mode
