B+ Tree and its concept
Date: 8 Oct 2006 17:36:09 -0700
Message-ID: <1160354169.513963.239630_at_e3g2000cwe.googlegroups.com>
Hi Everyone,
Here is a question that I came up while reading up on b+ trees. For some reason I am having a problem understanding some of the terms and the mechanical part of the tree.
So from what I understand, b+ tree is a representation of the index that was created from the data (data record). The tree has a root followed by several levels, each made up of NODES and then the leafs
(are leafs also called nodes?). The data stored in the leaf is known as
the DATA ENTRY which includes a search key and a RID (memory page #, slot #). The leafs are basically the last level of the tree which point to the actual data. An INDEX ENTRY is a combination <data, pointer>. A NODE is a combination of one or more Index Entries.
If the data record is in the same sorted order as the index entry, the b+ tree is clustered, which means less I/Os to find a retrieve data records.
Each node on the b+ tree including the root is at least 50% full.
(order of the tree)
The b+ tree representation of the index is stored in a file.
The internal nodes of a b+tree have n data and n+1 pointers.
So interms of I/O, since the b+ tree is stored in a file, if we want to access multiple data record, are we going to have multiple reads of the b+ tree file or is it that once you read the file, everything is held in memory and therefore, reducing the number of IOs.
also how is the order determined? Received on Mon Oct 09 2006 - 02:36:09 CEST