English
Menu

Data Structures and Algorithms

What is the main reason that B-trees (including B+ trees), rather than binary search trees, are widely used for indexes in databases and file systems?

  1. AEach node holds many keys, which keeps the tree shallow and narrows the range greatly with each node read, reducing the number of block reads from disk or similar storage
  2. BEach node holds only one key, so fewer comparisons are needed than in a binary search tree
  3. CThe tree does not need to be reshaped on insertion, so it is simpler to implement than a binary search tree
Show answer and explanation

Answer: A. Each node holds many keys, which keeps the tree shallow and narrows the range greatly with each node read, reducing the number of block reads from disk or similar storage

Disks and SSDs read data in blocks of several kilobytes even when only one byte is needed, so reducing the number of reads matters. A B-tree puts hundreds of keys into one node (one block), so each node read branches hundreds of ways; even 100 million records can be reached in 3 to 4 levels. When an insertion or deletion overfills a node it is split, and when a node becomes too empty it is merged, keeping all leaves at the same depth. A binary search tree with 100 million records needs at least about 27 levels, and reading a different block at each level is slow.

  • A. Correct. A high branching factor keeps the tree shallow and reduces the number of block reads.
  • B. Holding many keys per node is what characterizes a B-tree.
  • C. B-trees also reshape themselves by splitting and merging nodes, keeping all leaves at the same depth.
Practice this topic Back to topic

Related calculators

Sorting algorithm visualizerWatch 7 sorting algorithms (bubble, selection, insertion, shell, merge, quick and heap) step by step as bar charts, and compare their comparison and write countsDijkstra's algorithm calculatorCompute shortest paths and distances from a list of weighted edges, and follow each step of finalizing vertices in a table and a diagram

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

More Data Structures and Algorithms questions

  1. Which is an appropriate way to store in memory a sparse graph, one with few edges compared with its number of vertices, such as a road network with about 1 million vertices and 3 million edges?
  2. In a graph whose edges have no weights, you want to find the smallest number of edges from a starting vertex to every other vertex. Which pair of search method and data structure is suitable?
  3. In an undirected graph, the neighbors of each vertex are A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. A recursive depth-first search starts from vertex A. The neighbors are examined in the order listed, and as soon as an unvisited vertex is found, the search moves to it. In what order are the vertices visited?
  4. In an undirected graph, the edge weights (distances) are S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 and A−T: 6. Which shows the shortest path from S to T found by Dijkstra's algorithm and its length?
  5. Which condition on the graph is required for Dijkstra's algorithm to find correct shortest paths?