I can see adding a forward/reverse link to the tables making it a linked-list type structure much like your btree.
By default each node is linked to the one in front and back. Then you adjust those pointers for cut/paste operations. You could also do the cut/paste just by copying to a new table. If you want a disk-based B-Tree try this: http://www.die-schoens.de/prg/ Michael D. Black Senior Scientist NG Information Systems Advanced Analytics Directorate ________________________________ From: sqlite-users-boun...@sqlite.org [sqlite-users-boun...@sqlite.org] on behalf of Christopher Melen [relativef...@hotmail.co.uk] Sent: Monday, July 11, 2011 3:28 PM To: sqlite-users@sqlite.org Subject: EXT :Re: [sqlite] Storing/editing hierarchical data sets Many thanks for your neat, simple suggestion, Michael. Sometimes you can miss the wood for the btrees... Using tables seems a very attractive way to maintain such a hierarchy. The problem is that I need to be able to operate on the structure in a way not limited to just updating nodes and adding new ones. What I want to implement is a general cut/copy/paste mechanism - which is why I investigated btree-like data structures in the first place. Cutting and pasting in a btree is simple, often being no more than a matter of reorganizing a few pointers. A tree with a vast number of nodes (such as a typical b+tree) can be modified in this way with O(logN) efficiency. And in such a hierarchical arrangement as the one I require, localised changes are just as cheap, simply propagating up the tree to the root. What I am wondering, then (leaving aside the question of hierarchy), is if such a cut/copy/paste mechanism can be implemented using Sqlite tables, and if so how efficient is it likely to be? Might a virtual table created via ATTACH be useful here? Apologies for any naive assumptions - I've studied trees a lot but not so much SQL! Thanks, Christopher > From: michael.bla...@ngc.com > To: sqlite-users@sqlite.org > Date: Sun, 10 Jul 2011 19:41:07 +0000 > Subject: Re: [sqlite] Storing/editing hierarchical data sets > > Somebody smarter than I may be able to figure out how to use views to do the > upper levels. > > But if you can afford your database to be a bit less then twice as big just > use tables. > > > > create table level1(id int,l int,r int); > insert into level1 values(1,251,18); > insert into level1 values(2,5,91); > insert into level1 values(3,11,17); > insert into level1 values(4,54,16); > insert into level1 values(5,9,31); > insert into level1 values(6,201,148); > insert into level1 values(7,173,214); > insert into level1 values(8,43,66); > select max(l,r) from level1; > 251 > 91 > 17 > 54 > 31 > 201 > 214 > 66 > create table level2(id int,l int, r int); > insert into level2(l) select max(l,r) from level1 where rowid%2=1; > update level2 set r= (select max(l,r) from level1 where > level2.rowid=level1.rowid/2); > select * from level2; > id|l|r > |251|91 > |17|54 > |31|201 > |214|66 > create table level3(id int,l int, r int); > insert into level3(l) select max(l,r) from level2 where rowid%2=1; > update level3 set r= (select max(l,r) from level2 where > level3.rowid=level2.rowid/2); > select * from level3; > id|l|r > |251|54 > |201|214 > insert into level4(l) select max(l,r) from level3 where rowid%2=1; > update level4 set r= (select max(l,r) from level3 where > level4.rowid=level3.rowid/2); > select * from level4; > id|l|r > |251|214 > > > > Now let's update > > update level1 set l=90 where id=1; > > update level2 set l=(select max(level1.l,level1.r) where > level2.rowid=level1.rowid/2) > > update level2 set l= (select max(l,r) from level1 where > level2.rowid=(level1.rowid+1)/2); > > select * from level2; > > id|l|r > |90|91 > |17|54 > |31|201 > |214|66 > > update level3 set l=(select max(level2.l,level2.r) from level2 where > level3.rowid=level2.rowid/2); > > update level3 set l= (select max(l,r) from level2 where > level3.rowid=(level2.rowid+1)/2); > > select * from level3; > id|l|r > |91|54 > |201|214 > > update level4 set l=(select max(level3.l,level3.r) from level3 where > level4.rowid=level3.rowid/2); > > update level4 set l= (select max(l,r) from level3 where > level4.rowid=(level3.rowid+1)/2); > > select * from level4; > id|l|r > |91|214 > > > > Michael D. Black > > Senior Scientist > > NG Information Systems > > Advanced Analytics Directorate > > > > ________________________________ > From: sqlite-users-boun...@sqlite.org [sqlite-users-boun...@sqlite.org] on > behalf of Christopher Melen [relativef...@hotmail.co.uk] > Sent: Sunday, July 10, 2011 12:52 PM > To: sqlite-users@sqlite.org > Subject: EXT :[sqlite] Storing/editing hierarchical data sets > > > Hi, > > > I am developing an application which analyses audio data, and I have recently > been looking into Sqlite as a possible file format. The result of an analysis > in my application is a hierarchical data set, where each level in the > hierarchy represents a summary of the level below, taking the max of each > pair in the sub-level, in the following way: > > > 251 214 > > > 251 54 201 214 > > > 251 91 17 54 31 201 > 214 66 > > > 251 18 5 91 11 17 54 16 9 31 201 148 173 214 43 66 > > > Such a structure essentially represents the same data set at different levels > of resolution ('zoom levels', if you like). My first experiments involved a > btree-like structure (actually something closer to an enfilade* or counted > btree**), where the data stored in each node is simply a summary of its child > nodes. Edits to any node at the leaf level propagate up the tree, whilst > large edits simply entail unlinking pointers to subtrees, thus making edits > on any scale generally log-like in nature. This works fine as an in-memory > structure, but since my data sets might potentially grow fairly large (a few > hundred MB at least) I need a disk-based solution. I naively assumed that I > might be able to utilize Sqlite's btree layer in order to implement this more > effectively; this doesn't seem possible, however, given that the btree layer > isn't directly exposed, and in any case it doesn't map onto the user > interface in any way that seems helpful for this task. > > > I am aware of some of the ways in which hierarchical or tree-like structures > can be represented in a database (adjacency lists, nested sets, materialized > paths, etc.), but none of these seems to offer a good solution. What I'm > experimenting with at present is the idea of entering each node of the > hierarchy into the database as a blob (of say, 1024 bytes), while maintaining > a separate in-memory tree which then maps on to this flat database of nodes > (each node in the tree maintains a pointer to a node in the database). > > > I would be very interested in > thoughts/observations > on this problem - or even better a solution! > > > > Many thanks in advance, > Christopher > > > * http://en.wikipedia.org/wiki/Enfilade_(Xanadu) > ** http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html > > _______________________________________________ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > _______________________________________________ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users