[Resolved] maintaining SEQUENCE of child nodes...

sneakyimp

I am creating a database that encodes a hierarchical tree structure (kind of like the folders you see in windows explorer).

my records have a SEQUENCE column so that any collection of CHILDREN that have a common PARENT node can be sorted in an arbitrary order and that order can be stored and altered.

my question regards queries...when i'm adding a new child (think of creating a subfolder within another folder), i have to make sure the new child has a sequence number that is 1 higher than the highest existing sequence number. OR, if i'm inserting a new childe BEFORE an existing one, i need to increment the sequence number of all the children that occur after my inserted item.

is there a query that can simply return the highest existing sequence value or do i need to write a query to get all the children of a given parent node and FOR or WHILE through them to find the highest sequence number?

i considered using auto increment, but i want my users to eventually be able to re-order the objects and i want to store that new order. i don't know how to reset an autoincrementing value.

also, if anyone has any advice about how to keep these sequences CLEAN and make sure there are no HOLES, i would be profoundly grateful.

crimaniak

Don't use autoincrement.
Don't afraid holes. Holes must be part of algorithm. Think about. 🙂

sneakyimp

i finally found a query that will easily tell me the max value for sequence among a set of records...

SELECT MAX(sequence) WHERE blah blah blah

but your post was interesting, crimaniak. Are you suggesting that I should have large holes in there? If my sequence numbers are integers and my field accomodates 15 digit integers, there's a lot of room in there for widely spaced sequence numbers. i wouldn't necessarily have to keep updating the sequence numbers all the time....there might just be plenty of room between two adjacent items.

but this is also confusing...

nemonoman

I vote with crimaniak. Sequences with no gaps are the hobgoblin of little minds.

15 digits?
999,999,999,999,999

Let me know if you need more than a million billion nodes

sneakyimp

but...but....waaaaah!

alright alright....i know, there are only like 10²¹ subatomic particles in the entire universe or something....but it's one thing to mock a man for having a small mind, entirely another to bestow some kindness (and code) on him.

what might your algorithm look like for determining what sequence to give that is higher then the current node but less then the next node? Do you just add some fixed number to the sequence of the current node? wouldn't that approach just break down if you did it twice in a row?

how/when/how often do you check to make sure that your sequence is being properly maintained? that's where my confusion lies....ultimately, for me, this is all about avoiding tons of sql queries that a)i have to write and b) slow down performance when multiplied by N hits per second.

also, i can completely grasp the simple sequence models....small, adjacent integers whose sequences ARE precisely that...their order in the sequence.

gimme the zen (or the hole-y) lowdown on non-adjacent sequence numbers.

nemonoman

For sorting purposes, I use decimals.

For example:

1 FIRST ITEM
2 LAST ITEM

I want to insert middle item

I just take the average of the adjacent items and insert

INSERT INTO my table SET name='MIDDLE ITEM', sortorder=1.5

1 FIRST ITEM
1.5 MIDDLE ITEM
2 LAST ITEM

Beats hell out of integers.

1 FIRST ITEM
1.25 ABOVE MIDDLE ITEM
1.5 MIDDLE ITEM
1.75 BELOW MIDDLE ITEM
2 LAST ITEM

etc.

sneakyimp

aha!

brilliant. (and thanks).

that apparently eliminates the need to ever update all the sequence records in your database--or does it?? You are basically adding a digit with each new averaged value. How many digits are you permitted before you reach the limit? I guess it might depend on how you define your sequence column.

in mySQL, you have to specify how many digits your decimals can have and the more you specify, the larger your database becomes. based on your experience, what might be a safe value?

also, what might your query look like to obtain the next higher value? it would obviously be helpful for performance and coding purposes not to have to get ALL the records in your current group and have to iterate them to determine the value to average against.

nemonoman

Here's my real world:
Classified ads
Category: Transportation
Children: New Cars, Used Cars, Motorcycles....

I initially create the children in increments of 10

10 New Cars
20 Usec Cars
30 Motor Cycles

If new to be appended

SELECT max(sortorder) FROM category WHERE categoryname='Transportation'

Then

INSERT INTO category SET sortorder=$max * 10

etc.

Motorcycles should come before New Cars?

SELECT max(sortorder) FROM category WHERE categoryname='Transportation'
and sortorder < 10

$average=($under10 +10)/2
UPDATE category SET sortorder=$average

etc.

Everything is always ordered, but there is no specific sequence to the ordering

1
5.2
6.66666666
99
101.222222222
101.23
101.23333
19999.0020

etc.

I don't care how people move items around.

I think I use decimal 5,10 for my columntype

sneakyimp

thanks, nemonoman. you rock.

this problem is solved.
THANKS.

crimaniak

Originally posted by nemonoman

1
5.2
6.66666666
99
101.222222222
101.23
101.23333
19999.0020

etc.

I don't care how people move items around.

I think I use decimal 5,10 for my columntype [/B]

I am using INT type for it (because it's more fast) and garbage collecting. Garbage is unequality of intervals between items. When here is no space to insert new item child nodes are renumbered. In real situation (my forum) renumbering practically never occups.
I have article with complete alghoritm but in Russian only, sorry.

Addition:
You need garbage collector too because your case is equvivalent to my but numbers divided to 10000....
It's enought 32 or 64 (depends of..) inserts to existing sequense to reach the limit. Just insert items to one place and you will see it.
one more addition: if you insert last item in sequence use virtual item with number MAXINT.