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
what is the relationship between receipt and owner entities in computer sales and service company

What is a Phantom Deadlock? In distributed deadlock detection, the delay in propagating local information might cause the deadlock detection algorithms to recognize deadlocks

Define upgrade and downgrade? It gives a mechanism for conversion from shared lock to exclusive lock is called as upgrade. It gives a mechanism for conversion from exclusive

can you create a database for me in oracle/sql

Explain ER Relationship model? An entity-relationship model (ERM): An entity-relationship model (ERM) is an abstract theoretical illustration of structured data. Entity-relatio

What are the basic objects of the data dictionary? Tables Domains Data elements Structures Foreign Keys

Write short notes on Schema diagram. A database schema along with primary key and foreign key dependencies can be depicted pictorially by schema diagram. Every relation appears

What is trigger Triggers are statements that are implemented automatically by the system as the side effect of a change to the database.

What is the need of a log in a DBMS? Briefly describe the various types of records that are normally present in a log.            Ans:  The system log, which is generally writt

What is Conceptual Schema? Conceptual Schema - Conceptual schema elaborates the structure of the overall database for a community of users. It hides the details of physical sto