Somjit
Somjit

Reputation: 2772

What are Pointers in a B tree?

I'm having a hard time understanding what a 'pointer' is in a B-tree. Are they the same as an internal node of a Binary tree ?

If yes, why the different name ?
If not, how are they different ?

My confusion comes after reading this (Taken from wiki for B+ tree):

The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context — in particular, filesystems. This is primarily because unlike binary search trees, B+ trees have very high fanout (number of pointers to child nodes in a node,1 typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.

I have read in other SO posts that a B+ tree is a B tree where the 'pointers' don't hold data, only keys. So, whats this pointer ? And if someone could explain how there are such a high number of 'pointers' to a leaf node, that would be awesome :)

EDIT :

After the discussion in the comments section, things are starting to get clearer. However, in this highly up-voted answer to the difference between B trees and B+ Trees, the poster has put up an image, in which pink arrows are going out from the internal nodes. It says "pointers to data records" .. but aren't the data located in the leaves, so why pointers here ?

Upvotes: 0

Views: 4781

Answers (2)

Stian Jørgensrud
Stian Jørgensrud

Reputation: 1024

I think you get confused because you have read that in a B+ tree all the pointers in internal nodes points to other blocks/nodes in the tree. You can call them tree pointers, if you want. Pointers in the leaf nodes points to data records or blocks, (except for the pointer to the next leaf node). You can call these data pointers, if you want.

So you can say the pointers point to two different things; nodes or data, but that is just a way of organizing your thoughts. The pointers are still just regular pointers, pointing to some kind of data.

Source: Fundamentals of Database Systems (6th Edition) 6th Edition by Ramez Elmasri (Author), Shamkant B. Navathe (Author)

Upvotes: 0

XapaJIaMnu
XapaJIaMnu

Reputation: 1502

The wiki entry talks about the difference between a binary tree and a btree. In a binary tree each parent has 2 children: One greater than the other and one smaller. In the btree each parent can have many children (this is the high fanout in the wikipedia article) and the connection from this parent to each child is realised through pointers. Section of a btree

Here is a section of a btree. As you can see the node "944; 1011; 1037; 1087" has 5 children and hence 5 pointers to different nodes. This is what the wikipedia quote is talking about. If that were a binary tree each level would have only 1 key and 2 children.

Upvotes: 3

Related Questions