Indexing Structures (B+Tree)

Sorta database related =); Query Question

Page 1 of 1

5 Replies - 3502 Views - Last Post: 09 April 2009 - 08:08 AM Rate Topic: -----

#1 killnine  Icon User is offline

  • D.I.C Head

Reputation: 19
  • View blog
  • Posts: 161
  • Joined: 12-February 07

Indexing Structures (B+Tree)

Posted 09 December 2008 - 09:15 AM

Hey guys,
I hope this is in the right section. It's more of a generic indexing structure question, but I felt it went pretty well in the databases section.

My question comes from a question my professor asked me earlier this week. We have been studying B+-Trees and can see how they are efficient at insertion and deletion in certain conditions.

Typically I think of using a tree when I want to find a distinct value.


HOWEVER, my professor asked me how many instructions it would take to process a query for something like 'values less than x'.

So I have just hotlinked a google image and was hoping someone could expain this to me

Posted Image

if I wanted to find all the values less than 7 in this B+tree, would it take two operations to get to the leaf nodes, and another operation to travel through each leaf node until the value is not less than 7?

*shrug*

Hopefully someone can help out because I know this sort of thing is going to be on my final.

This post has been edited by killnine: 09 December 2008 - 09:18 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Indexing Structures (B+Tree)

#2 Martyr2  Icon User is offline

  • Programming Theoretician
  • member icon

Reputation: 4354
  • View blog
  • Posts: 12,160
  • Joined: 18-April 07

Re: Indexing Structures (B+Tree)

Posted 09 December 2008 - 02:07 PM

You are exactly correct. B+trees are good for range queries in that you can quickly find a value in a given range, by traversing down the tree into the leaves, then moving through the leaves, sometimes going from branch to branch.

So for example (using your graphic), to find the values of less than 7 you would do a search for the value 2 (which will always be equal to the depth of the tree which in this instance is 2) to find the value 2 and then iterate 2...3...5 and then you are going to jump through the pointer over to 7. Once you hit the upperbound the operation completes and you have your answer of 3, 3 nodes are less than 7.

So why is this all a big deal over a standard binary tree? Size. Notice the depth of this tree, to reach any leaf here you are going to have the max of 2 operations. Compare this to a binary tree which can be much much taller and take as many as 10 operations just to find one value. During the insert into a B+tree if the value is going to overflow the range of leaves a node can have (also referred to as the block size) it will split the branch and create a new one of equal block size. You will also hear this as the node being "full".

So you never increase the depth, but it can get wider and wider and wider. With the total width being equal to the number of branches and its block size.

File systems like NTFS and others use this method because you can virtually find anything with the same number of operations. This is how Google essentially can fetch any page of billions of indexes so quickly. Their nodes however are actual index servers.

Hopefully I have made it a bit more clear.

:)
Was This Post Helpful? 0
  • +
  • -

#3 Trogdor  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 15
  • View blog
  • Posts: 627
  • Joined: 06-October 06

Re: Indexing Structures (B+Tree)

Posted 10 December 2008 - 06:48 AM

A little off topic, but i heard 10 years ago of a variation on the B+ tree: the W tree.
The only difference being that the index layers are horizontally linked.
So the index node marked 7 is linked to the index node marked 23-31-43 and viceversa.
Allegedly this is helpfull when traversing a tree in a range operation, since you do not need to backtrack upwards.
Also easy for streaming out the complete structure.
Not sure if this idea has ever seen an application, but it just popped up in my head when reading this thread.
Was This Post Helpful? 0
  • +
  • -

#4 shahin55  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 24-March 09

Re: Indexing Structures (B+Tree)

Posted 25 March 2009 - 12:40 AM

can you provide me a small sample code on btree
Was This Post Helpful? 0
  • +
  • -

#5 dlm58  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 08-April 09

Re: Indexing Structures (B+Tree)

Posted 08 April 2009 - 03:13 PM

I see that you ave composed an image of a B+ Tree. I was just wondering how to do that. Is there a template with boxes and lines connecting nodes. What software was used. I appreciatte any help very much.



View Postkillnine, on 9 Dec, 2008 - 08:15 AM, said:

Hey guys,
I hope this is in the right section. It's more of a generic indexing structure question, but I felt it went pretty well in the databases section.

My question comes from a question my professor asked me earlier this week. We have been studying B+-Trees and can see how they are efficient at insertion and deletion in certain conditions.

Typically I think of using a tree when I want to find a distinct value.


HOWEVER, my professor asked me how many instructions it would take to process a query for something like 'values less than x'.

So I have just hotlinked a google image and was hoping someone could expain this to me

Posted Image

if I wanted to find all the values less than 7 in this B+tree, would it take two operations to get to the leaf nodes, and another operation to travel through each leaf node until the value is not less than 7?

*shrug*

Hopefully someone can help out because I know this sort of thing is going to be on my final.

Was This Post Helpful? 0
  • +
  • -

#6 Trogdor  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 15
  • View blog
  • Posts: 627
  • Joined: 06-October 06

Re: Indexing Structures (B+Tree)

Posted 09 April 2009 - 08:08 AM

looks to me like it was done in something like paint.
Visio would do the job nicely, if you allow that kind of programs to inhabit your harddisk.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1