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
Define a table in SQL known as Client that is used to store information about the clients. Define CLIENT_NO as the primary key whose first letter must begin with ‘C'. Also ensure t

Sequential File Organisation The most necessary way to organise the collection of records in a file is to use sequential Organisation. Records of the file are stored in series

Explain DML with some examples? DML - Data Manipulation Language: statements used for managing data within schema objects. Some examples: • SELECT - retrieve data from the a da

What is data block? Data Block - In oracle the data blocks are referred to as tablespaces. A tablespace is an fields of disk consisting of one or more disk files. A tablespace

What is the use of with clause in SQL? The with clause gives a way of defining a temporary view whose explanation is available only to the query in which the with clause occurs

Describe file organisation? A file is organized logically as a sequence of records. These records are mapped onto disk blocks. A) Fixed-Length Records Type deposit=record

Relational and E-R Model There are three types of constraints on relational database that have: DOMAIN CONSTRAINT PRIMARY KEY CONSTRAINT INTEGRITY CONSTRAINT

please describe the data base management with the easy example &give the application?

You are required to write a report which evaluates two of the following issues in relation to your case study database: a. Security issues b. Performance issues c. Backup

Replication : It is definite as a copy of a relation. Every replica is stored at a dissimilar site. The alternative to replication is to store only single copy of a relation which