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 ?
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.
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.