SQL Server Mentalist

Hi Folks,

This post is part of Series Database Management Systems

Currently running topic for this series is listed as below :

Series of Database Management Systems

>>Chapter 1 : DBMS [Database Management Systems]

>>Chapter 2 : Database Core Concepts and  Applications

>>Chapter 3 : Record Storage and Primary File Organization

>>Chapter 4 : Index Structures of Files<You are Here>

Continuing from my previous post on this series.

We are going to Cover the Following Points in this article

• Multilevel Indexes
• B+Tree Index Files
• B-Tree’

Multilevel Indexes

Indexes with two or more levels are called multilevel indexes. The idea behind a multilevel index is to reduce search time required for searching the whole data file. A multilevel index considers the index file which will be referred to as the first level of a multilevel index, as an ordered file with a distinct value for each k(i). Hence we can create a primary index for the first level; this index to the first level is called the second level of multilevel index. Because the second level is a primary index, we can use block anchors so that the second level has one entry for each block of the first level.

Figure A two-level primary index resembling ISAM (Indexed Sequential Access Method) organization

B+Tree Index Files

The main disadvantage of the index-sequential file organization is that performance degrades as the file grows. A B+-tree index takes the form of a balanced tree in which every path from the root of the tree to a leaf of the tree is of the same length.

In a B- tree every value of the search field appears once at some level in the tree, along with a data pointer [may be in internal nodes also]. In a B+-tree, data pointers [address of a particular search value] are stored only at the leaf nodes of the tree; hence, the structure of leaf nodes differs from the structure of internal nodes. The leaf nodes have an entry for every value of the search field, along with a data pointer to the record.

A B+ tree is a multilevel index, but it has got different a structure. A typical node of the B+ tree contains upto n-1 search key values such as k1,k2…….n-1 and n pointers p1,p2…..pn. The search key values within a node are kept in sorted order, ki < kj.

The number of pointers in a node is called the fan out of the node.

Ø The structure of a non-leaf node is the same as leaf nodes, except that all pointers are pointers to tree nodes.

Ø Each internal node is of the form >p1, k1,p2,k2….pq-1, kq-1, pq>

Ø The root node has at least 2 tree pointers.

Ø Each leaf node is of the form

<<k1, pr1>,<k2, pr2>……<kn-1, prn-1>, pnext>

each pri is a data pointer, and pnext points to the next leaf node of the

B+ tree

Ø All leaf nodes are at the same level.

Consider an example, assume that we wish to insert a record in a B+ tree of order n=3 and pleaf=2, first we observe that root is the only node in the tree, so it is also a leaf node. As soon as more than one level is created, the tree is divided into internal nodes and leaf nodes. Notice that every value must exist at the leaf level, because all the data pointers are at the leaf level. However, only some values exist in internal nodes to guide the search. Notice also that every value appearing in an internal node also appears in the sub tree as the rightmost value.

Say for example, to insert 12, the node is split into two nodes.

The figure shows the two leaf nodes that result from inserting 12. An existing node contains 7 and 8 and remaining value 12 in a new node. The first J = [((Pleaf + 1)1/2)] = 3/2 = 2 entries in the original node are kept there and the remaining entries are moved to a new leaf node. The J th search value is replicated in the parent internal node, and an extra pointer to the new node is created in the parent. If the parent internal node is full, it must be split. This splitting can propagate all the way up to create a new root node.

Figure An example of insertion in a B+ tree with p=3 and Pleaf=2

B-Tree’

B – Tree indexes and similar to B+ tree indexes. The main difference is that a B tree eliminates the duplicate storage of search – key values. In the B+ tree every search key value appears in some leaf nodes and several are repeated in non-leaf nodes. AB – tree allows search – key values to appear only once, hence B – tree requires fewer nodes. However, since the search-keys appear only once, in a B – tree, every node contains search value along with an address of that value [pointer point either to file records or to buckets that contain the search value].

Figure B- tree structures. (a) A node in a B- tree with q-1 search values

(b) A B- tree of order P=3. The values were inserted in the order 8, 5, 1, 7, 3,

12, 9, 6.

Consider figure B, in the values 5, 8, 1, 3, 6, 7, 9, 12 are values of the indexed filed. Consider the top node, which consists of two value entries [5 and 8] and three pointers. Values less than 5 or equal to 5 are placed in the left lower node, similarly values greater than 5 and less than 8 are placed in the middle node, and greater than 8 are placed in the right lower node.

Consider an algorithm of B-trees. Set N to the top node

Let X, Y be the data values in node N [x<y]

If V<=X

Then set N to the left lower node of N If X, V <=Y

Then set N to middle lower node of N If V > Y

Then set N to right lower node of N End

If V occurs in node N then exit [found]

If V does not occur in node N then exit [not found]

A B – tree starts with a single root node [which is also a leaf node] at level 0 [zero]. Once the root node is full with p – 1 search key values, we attempt to insert another entry in the tree, the root node splits into two nodes at level 1. Only the middle value is kept in the root node, and the rest of the values are split evenly between the other two nodes. When a non root node is full and a new entry is inserted into it, that node is split into two nodes at the same level, and the middle entry is moved to the parent node along with two pointers to the split nodes. If the parent node is full, it is also split. Splitting can propagate all the way to the root node.

Advantage:

B tree eliminates the redundant storage of search key values.

Disadvantage:

Deletion in a B tree is more complicated. In a B+ tree, the deleted entry always appears in a leaf. In a B tree, the deleted entry may appear in a non-leaf node.

Hope you will like Series of Database Management Systems series !

If you have not yet subscribe this Blog , Please subscribe it from “follow me” tab !

So that you will be updated @ real time and all updated knowledge in your mail daily for free without any RSS subscription OR news reading !!

Happy Learning and Sharing !!

For More information related to BI World visit our all Mentalist networks Blog

SQL Server Mentalist … SQL Learning Blog

Business Intelligence Mentalist … Business Intelligence World

Microsoft Mentalist … MVC,ASP.NET, WCF & LinQ

MSBI Mentalist … MS BI and SQL Server

NMUG Bloggers …Navi Mumbai User Group Blog

Architectural Shack … Architectural implementation and design patterns

DBA Mentalist …Advance SQL Server Blog

MVC Mentalist … MVC Learning Blog

Link Mentalist … Daily Best link @ your email

Infographics Mentalist … Image worth explaining thousand Words

Hadoop Mentalist … Blog on Big Data

BI Tools Analysis … BI Tools

Connect With me on

| Facebook |Twitter | LinkedIn| Google+ | Word Press | RSS | About Me |