0

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 ?

Community
  • 1
  • 1
Somjit
  • 2,503
  • 5
  • 33
  • 60
  • 1
    Pointers are nothing B tree specific, they're a very general programming concept. –  Apr 15 '15 at 07:08
  • i know the general pointer, i wanna know if its something else in this context – Somjit Apr 15 '15 at 07:08
  • 1
    Why would you think it's something else? – user2357112 Apr 15 '15 at 07:09
  • please see my edited question. Thats where i'm getting stuck. – Somjit Apr 15 '15 at 07:13
  • Why do you think the quote you've given describes anything different from an ordinary pointer? – user2357112 Apr 15 '15 at 07:15
  • Umm.. in a binary tree, there is only one pointer to a leaf node, the one coming from the parent node. So.. how can there be so many pointers to a single leaf node ? Yes , its not a Binary tree, but there should still be just one link between a parent and a leaf right ? That's what made me think its something else... – Somjit Apr 15 '15 at 07:18
  • 2
    It's not many pointers to *one* leaf - it's many pointers, each pointing to a *different* child. Even if there were a ton of pointers to the same node, though, that still wouldn't be reason to think these are some new kind of pointer. Different pointers can point to the same thing. – user2357112 Apr 15 '15 at 07:19
  • edited my post. the final reason why i thought these are something different, can you take a look ? – Somjit Apr 15 '15 at 07:31
  • 1
    Tree indexes to data on block-oriented mass storage with high latency exist to minimise the number of ("random") accesses. To this end, the nodes need to contain enough _key_ data for navigation and references to further data: _pointers_. There may be two kinds of the latter: pointers to further index nodes/blocks (which figure in, e.g., the _arity_) and pointers to full data records. – greybeard Apr 15 '15 at 07:37
  • When they say data is "in" the leaves or "in" internal nodes, they don't mean that in terms of raw storage layout. It's fairly common to say that data is "in" some part of a data structure when that part of the data structure actually holds a pointer to the data. – user2357112 Apr 15 '15 at 09:02
  • So a lot of answers and comments here. So, is everything clear or you have some question still? – Msk Apr 15 '15 at 18:08

2 Answers2

3

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.

XapaJIaMnu
  • 1,408
  • 3
  • 12
  • 28
  • @XapaJlaMnu:How is this useful? – Micromega Apr 15 '15 at 12:09
  • 3
    @Phpdna It answers the question?! Why would you downvote me for that? You answer the question in a way only someone who is familiar with btrees can understand. The OP I think couldn't grasp what pointers were talked about. Also I didn't downvote your post... – XapaJIaMnu Apr 15 '15 at 12:13
0

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)

Stian Jørgensrud
  • 662
  • 6
  • 14