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 a data warehouse, Problem 1 What is a Data Warehouse? Mention i...

Problem 1 What is a Data Warehouse? Mention its advantages 2 Explain the Top-Down and Bottom-up Data Warehouse development Methodologies 3 What is Data Transformation? Ex

What are the concurrency issues, Concurrency issues Data integrity...

Concurrency issues Data integrity: Threads accessing same object need to be synchronized, such as: banking account. Deadlock: One or more threads in system are perman

Hashing techniques, folding method and mid square method using visual basic...

folding method and mid square method using visual basic

Joins, how can apply joins on table

how can apply joins on table

Relational database, Consider the following relational database: STUDENT (n...

Consider the following relational database: STUDENT (name, student#, class, major) COURSE (course name, course#, credit hours, department) SECTION (section identifier, course#, sem

Functional dependencies and normalization for relational dat, Consider the ...

Consider the 1ollowin8 relation: CAR SALE (Car_id, Option_type, Option_listprice, Sale_date, Option_discountedprice) This relation refers to options installed in cars (e.g., crui

Explain the term - handling boundary condition, Explain the term - Handling...

Explain the term - Handling Boundary Condition These are some circumstances that to be handled in any system initialization and termination. Describes how system is bro

What is a select operation, What is a SELECT operation? The select oper...

What is a SELECT operation? The select operation selects tuples that please a given predicate. We use the lowercase letter σ to denote selection.

Record based logical models, Record based Logical Models: Use records as th...

Record based Logical Models: Use records as the key data representation components Examples: Relational Model: It shows data as well as relationship between data in the form

Problem about data mining for business intelligence, Do the 11.1 11.1 Cre...

Do the 11.1 11.1 Credit Card Use. Consider the following hypothetical bank data on consumers’ use of credit card credit facilities in Table 11.3. Create a small worksheet in Exce

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