Index and tree structure, Database Management System

Index And Tree Structure

Let us talk about the data structure that is used for creating indexes.

Can we use Binary Search Tree (BST) as Indexes?

Let us initial reconsider the BST. A binary search tree is a data structure that has a property that all the keys that are to the left of a node are lesser than the key value of the node and all the keys to the right are bigger than the key value of the node.

To search a typical key value, you begin from the root and move in the direction of left or right depending on the value of key that is being searched. As an index is a pair, therefore while using BST, we require to use the value as the key and address field must also be specified in order to locate the data in the file that is kept on the secondary storage devices. The given figure demonstrates the use of BST index for a University where a dense index exists on the enrolment number field.


                           1451_Index And Tree Structure.png


                                  Figure: The Index structure using Binary Search Tree


Please note in the figure above that a key value is related with a pointer to a record. A record includes of the key value and other information fields. Though, we don't store these information fields in the BST, as it would make a very large tree. Therefore, to speed up searches and to reduce the tree size, the information fields of records are usually stored into files on secondary storage devices. The connection among key values in the BST to its corresponding record in the file is recognized with the help of a pointer as shown in Figure. Please note that the BST structure is address pair, key value.

Now, let us study the suitability of BST as a data structure to execute index. A BST as a data structure is very much fit for an index, if an index is to be contained totally in the primary memory. Though, indexes are bit large in nature and need a combination of primary and secondary storage. As far as BST is concerned it may be stored level by level on a secondary storage which would need the additional problem of finding the correct sub-tree and also it may need a number of transfers, with the worst condition as one block transmit for every level of a tree being searched. This situation can be drastically remedied if we use B -Tree as data structure.

A B-Tree as an index has two benefits:

  • It is completely balanced
  • Every node of B-Tree can have a number of keys. Ideal node size would be if it is somewhat equivalent to the block size of secondary storage.

The question that required to be answered here is what should be the order of B-Tree for an index. It ranges from 80-200 depending on several index structures and block size.

Let us recollect some essential facts about B-Trees indexes.

The basic B-tree structure was discovered by E.McCreight and R.Bayer (1970) of Bell Scientific Research Labs and has become one of the famous structures for organising an index structure. Lots of variations on the basic B-tree structure have been developed.

The B-tree is a useful balanced sort-tree for external sorting. There are strong uses of B-trees in a database system as pointed out by D. Comer (1979): "While no one scheme can be optimum for all applications, the methods of organising a file and its index known as the B-tree is the standard Organisation for indexes in a database system."

A B-tree of order N is a tree in which:

  • Every node has a maximum of N children and a minimum of the ceiling of [N/2] children. Though, the root node of the tree can have 2 to N children.
  • Every node can have one fewer keys than the number of children, but a maximum of N-1 keys can be kept in a node.
  • The keys are normally in order in an increasing order. All keys in the sub tree to the left of a key are less than the key, and all the keys in the sub-tree to the right of a key are higher than the value of the key.
  • If a new key is inserted into a full node, the node is dividing into two nodes, and the key with the median value is inserted in the parent node. If the root is the parent node then a new root node is produced.
  • All the leaves of B-tree are on the similar level. There is no empty sub-tree above the level of the leaves. Therefore a B-tree is completely balanced.
Posted Date: 3/8/2013 6:15:04 AM | Location : United States

Related Discussions:- Index and tree structure, Assignment Help, Ask Question on Index and tree structure, Get Answer, Expert's Help, Index and tree structure Discussions

Write discussion on Index and tree structure
Your posts are moderated
Related Questions
Explain briefly concurrent task by taking an example. Concurrent Task- The concurrent occurrence of more than one event is called concurrent task. Operating systems can handl

Problem : AirwaysCentre, an international airline booking company currently uses a relational database system for their operations, which includes the following relations: P

What is Secondary Index While making the index, generally the index table is kept in the primary memory (RAM) and the main table, because of its size is keeps in the secondary

Deadlock Prevention One of the easiest approaches for avoiding a deadlock would be to obtain all the locks at the begin of the transaction. Though, this approach restricts conc

Write short notes on relational model   The  relational  model  uses a  collection of  tables  to show  both data  and the relationships between those  data.  The relational mo

Project Description: Hi I'm seeking someone to make my dBase application work. I know it's not a 'modern' language but it's what I know. I have written an order program and I ne

Gyan Gurukul is a software company that provides software related solution. Ashutosh Dubey who is the director of Gyan Gurukul want a three-level schema architecture for the Gyan G

The Structured Query Language INTRODUCTION Database is an organised set of information about an entity having controlled redundancy and serves numerous applications. DBMS