Basic CS-Data Structures [TCS Placement]: Sample Questions 26 - 26 of 28

Get unlimited access to the best preparation resource for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.

Question 26

Data Structures

Describe in Detail


In RDBMS, what is the efficient data structure used in the internal storage representation?


B + tree.

  • In B + tree, all the data is stored only in leaf nodes, making searching easier.
  • The B + Tree is called a balanced tree because every path from the root node to a leaf node is the same length, thus requiring the same number of nodes to be read from the disc.
  • The B + Tree consists of two types of nodes
    • Internal nodes: Internal nodes point to other nodes in the tree
    • Leaf nodes: Point to data in the database using data pointers. Leaf nodes also contain an additional pointer, called the sibling pointer, which is used to improve the efficiency of certain types of search.
  • All the nodes in a B + Tree must be at least half full except the root node which may contain a minimum of two entries.
  • Algorithms inserting and deleting data from a B + Tree guarantee each node will be at least half full.
  • Searching for a value in the B + Tree starts from root and moves downwards until it reaches a leaf node.
  • Both internal and leaf nodes contain key values that are used to guide the search for entries in the index. This is shown in the diagram
Given the Image is Define the B + Tree Structure

Developed by: