binary tree calculation

Question

Post reply

binary tree calculation

s.khann786

Old Hand

Points: 347
More actions
July 26, 2011 at 3:38 am

#240572

hi
i am working on mlm for that i need to calculate parent who have left and right child.
can any one give me database structure for mlm
thanks in advance.
Please give some solution.

Viewing 11 posts - 1 through 10 (of 10 total)

You must be logged in to reply to this topic. Login to reply

spaghettidba SSC Guru Points: 105732 More actions · Answer 1

In SQL Server 2008 you can use the HierarchyId datatype to store tree structures.

AFAIK, MLM is illegal in many countries (including Italy).

Be careful what you do.

-- Gianluca Sartori

s.khann786 Old Hand Points: 347 More actions · Answer 2

i am creating binary mlm project i have no idea about it

i got query about how to calculate left and right child.

but i need to calculate numbers of pairs in my binary tree.

my table

id, leftid, rightid,

1 2 3

2 4 5

3 6 N(no child)

4 8 9

Jeff Moden SSC Guru Points: 1003873 More actions · Answer 3

If it's a simple count of pairs you want, just look at your data for the answer. Just count all rows that have both a LeftID AND RightID greater than 0 (which will take care of NULLs, as well).

If you want something else, you'll have to be more explicit about what it is that you want.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

s.khann786 Old Hand Points: 347 More actions · Answer 4

Dear Jeff,

i want to calculate parents id which have both child left and right.

this is my table.

id, parentid, left_child, right_child

1 1 2 3

2 2 4 5

3 3 6 7

4 4 8 N

5 5 10 12

more..........

if i pass query to calculate parent which have both child it calculate. but the problem is if i want to calculate parent which have both child indside parentid 4 it will calculate all below parents but it is not necessary that below child is inside parentid 4.

please healp me.

thank in advance.

Jeff Moden SSC Guru Points: 1003873 More actions · Answer 5

s.khann786 (7/31/2011)
Dear Jeff,
i want to calculate parents id which have both child left and right.
this is my table.
id, parentid, left_child, right_child
1 1 2 3
2 2 4 5
3 3 6 7
4 4 8 N
5 5 10 12
more..........
if i pass query to calculate parent which have both child it calculate. but the problem is if i want to calculate parent which have both child indside parentid 4 it will calculate all below parents but it is not necessary that below child is inside parentid 4.
please healp me.
thank in advance.

Hmmm... OK, I believe I understand that. Can you provide a little more data (a level or two deeper than ParentID 4). It would be real handy for me if you posted the data following the methods shown by the article at the first link in my signature line below.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Jeff Moden SSC Guru Points: 1003873 More actions · Answer 6

Gianluca Sartori (7/26/2011)
In SQL Server 2008 you can use the HierarchyId datatype to store tree structures.

@Gianluca,

Since you brought it up, I have to ask... have you used the HierarchyID datatype for anything? If so, what do you think about it? I ask because I've heard tales of performance problems and somewhat cumbersome code and I've not done any research on it one way or another, yet. That's part of the holdup on the article about hierarchies that I'm slowly working on.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

spaghettidba SSC Guru Points: 105732 More actions · Answer 7

Jeff Moden (7/31/2011)
Gianluca Sartori (7/26/2011)
In SQL Server 2008 you can use the HierarchyId datatype to store tree structures.
@Gianluca,
Since you brought it up, I have to ask... have you used the HierarchyID datatype for anything? If so, what do you think about it? I ask because I've heard tales of performance problems and somewhat cumbersome code and I've not done any research on it one way or another, yet. That's part of the holdup on the article about hierarchies that I'm slowly working on.

I'm sorry Jeff, I have never used it for production code. I'm stuck in 2005 here and I have just played with it on my laptop.

I didn't encouter performance problems, but I didn't play with enough data either.

Probably I shouldn't have suggested something I don't master, to tell the truth.

-- Gianluca Sartori

HLogic SSC-Addicted Points: 435 More actions · Answer 8

Jeff,

I have tested the HierarchyID and associated functions against Adjacency Lists using CTE's, Nested Sets (a la Celko) and Nested Intervals (Hazel's implemetation) and found it to be lacking in the performance realm. I am reasonably certain it is due to the use of Materialized Path in the implementation.

I managed to implement Hazel's Nested Intervals using Rational Numbers method, in concert with a CLR function :w00t: to generate larger scope DECIMAL() values and was able to expand the tree depth substantially with little performance impact.

EDIT:

Note: Although an implementation has been created and tested, it has not been used in a production environment. It is not one of the more commonly known nor readily understood techniques.

I would have to dig up the exact numbers but if I recall correctly Hazel's method was about 4x more performant overall and an order of magnitute more performant with INSERTs.

Jeff Moden SSC Guru Points: 1003873 More actions · Answer 9

HLogic (8/1/2011)
Jeff,
I have tested the HierarchyID and associated functions against Adjacency Lists using CTE's, Nested Sets (a la Celko) and Nested Intervals (Hazel's implemetation) and found it to be lacking in the performance realm. I am reasonably certain it is due to the use of Materialized Path in the implementation.
I managed to implement Hazel's Nested Intervals using Rational Numbers method, in concert with a CLR function :w00t: to generate larger scope DECIMAL() values and was able to expand the tree depth substantially with little performance impact.
EDIT:
Note: Although an implementation has been created and tested, it has not been used in a production environment. It is not one of the more commonly known nor readily understood techniques.
I would have to dig up the exact numbers but if I recall correctly Hazel's method was about 4x more performant overall and an order of magnitute more performant with INSERTs.

Very cool information. That certainly lets me know what to expect.

You do have me at a disadvantage, though. I'm not familiar with "Hazel's method". Do you have a particular/recommended link I should look at or will a trip to Google satisfy my curiosity?

Also, you say Hazel's method was about 4x more peformant overall... while I know the meaning of the word "overall", I just want to be sure... does that mean it's also 4x faster than classic Nested Sets?

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

HLogic SSC-Addicted Points: 435 More actions · Answer 10

The URL to Hazel's method: http://arxiv.org/PS_cache/arxiv/pdf/0806/0806.3115v1.pdf

The "overall" was in reference to HierarchyID. However, Nested Intervals outperformed Nested Sets in everthing related to non-leaf node (insertion, promotion, demotion, deletion) except subordinate node retrieval. Leaf node manipulation (insertion, deletion, 'move to' as another leaf node) was the essentially the same. As a side note, retrieving the parent node ratiional keys with the NI method does not require a trip to the DB - it's an iterative calculation.

I like the NI method but it takes a little effort to get your head wrapped around the 'look and feel' and a little more to be able to look at raw data and 'see' the hierarchy. Of course that may be just me and the damage my head sustained in years gone by...