Index and tree structure, Database Management System

Assignment Help:

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.

Related Discussions:- Index and tree structure

What is view in sql, What is view in SQL? How is it defined? Any relati...

What is view in SQL? How is it defined? Any relation that is not part of the logical model, but is made visible to a user as a virtual relation is known as a view. We descri

One to many - relationship cardinality, One-to-many : An entity in A is rel...

One-to-many : An entity in A is related with any number of entities in B. An entity in B is related with at the most one entity in A. Example: Relationship between faculty and d

Define thomas write rule, Define Thomas write rule Thomas' write rule: ...

Define Thomas write rule Thomas' write rule: The Thomas' write rule is a modification of timestamp-ordering protocol for concurrency control. Assume that transaction T i issue

Define query by example, Define Query by Example QBE is a query languag...

Define Query by Example QBE is a query language relies upon domain calculus and has two dimensional syntax. The queries are written in the horizontal and vertical dimensions of

Define tables students and teachers as sub tables of people, Write a query ...

Write a query to define tables students and teachers as sub tables of people? Create table students of student under people Create table teachers of teacher under people

Describe the storage structure of indexed sequential file, Describe the sto...

Describe the storage structure of indexed sequential files and their access method. Ans: Index offers a lookup capability to rapidly reach the vicinity of the desired record.

Create a new user-data control, Create a new user : CREATE USER IDENTI...

Create a new user : CREATE USER IDENTIFIED BY Example: //CREATE USER MCA12 IDENTIFIED BY W123 Grant: It is used to give database access permission to users. It is of

What is d command work in the respect of qbe, What is D command work in the...

What is D command work in the respect of QBE? D: It is the command inside QBE to delete tuple(s) from the relation.

What is structured query langauge, What is Structured Query Langauge (SQL)?...

What is Structured Query Langauge (SQL)? SQL is a powerful set-oriented language which was formed by IBM research for the databases that adhere to the relational model. It havi

Assignments, i have assignments I don''t have time to finish because of wo...

i have assignments I don''t have time to finish because of work and other assignments, can you help with this? All are from the book Darabase design, application development and a

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd