Coursify

B+ Trees: Random vs Sequential Access (Which Statement Is True?)

B+ Trees: Random vs Sequential Access (Which Statement Is True?)

Verified Sources
Sep 12, 2026

B+ Tree Explained (Search, Insertion, Deletion) + Linked Leaves for Range Queries

A B+ tree is a balanced multi-way search tree used heavily in database indexes because it stores actual records in leaf nodes and links those leaves to support efficient ordered traversal. In particular, its linked leaf structure makes range queries and sequential iteration efficient: once you locate the starting key via an O(log⁡n)O(\log n) descent, you can scan forward through adjacent leaves instead of repeatedly re-traversing the tree structure.

Key idea for this question:

  • Random access (point lookups) is efficient because height is logarithmic (search descends root → leaf).
  • Sequential access / ordered scans are also efficient because the leaves are connected (a linked list), enabling “next” access across keys.2

Therefore, among the given options, the true statement is the one claiming rapid random access and rapid sequential access for B+ trees.

Footnotes

  1. B+ tree - Wikipedia - Describes linked leaves and how it simplifies efficient range queries/ordered iteration. ↩ ↩2

  2. B+ Tree - Data Structures Tutorial | Study Glance - Notes properties: data in leaf nodes; leaves linked; internal nodes route search. ↩

B+ Tree properties that matter for the options

We’ll connect each property to the answer choices.

linked-list leaves
range query
point lookup
fan-out

  1. Point lookups (random access) are fast because B+ trees are height-balanced; lookups require descending from root to the correct leaf, which is logarithmic in the number of keys.2
  2. Ordered scans (sequential access) are fast because B+ tree leaves are “often linked… in a linked list; this makes range queries… and ordered iteration simpler and more efficient.”
  3. Range-query scanning cost is typically described as: find the start with O(log⁡n)O(\log n), then read/report kk qualifying entries by scanning along the leaf chain (often expressed as O(log⁡n+k)O(\log n + k)).

Mermaid intuition:

Footnotes

  1. B-Tree, B+ Tree & Red-Black Tree: Types (2026) | PerfectNotes - Explains that B-trees are wide/shallow and yield O(log⁡n)O(\log n) searches and that B+ trees keep data in leaf nodes. ↩

  2. B+ Tree - Data Structures Tutorial | Study Glance - Notes properties: data in leaf nodes; leaves linked; internal nodes route search. ↩

  3. B+ tree - Wikipedia - Describes linked leaves and how it simplifies efficient range queries/ordered iteration. ↩

  4. B+ Tree Visualizer | Linked-Leaf Multi-Way Search Tree - States range queries: O(log⁡n)O(\log n) to find start key, then linear scan along leaf chain; summarizes O(log⁡n+k)O(\log n + k). ↩

Evaluate each option against B+ tree access behavior

  1. 1
    Step 1

    Random access corresponds to point lookups; sequential access corresponds to ordered/range scans across keys.

  2. 2
    Step 2

    This contradicts the linked-leaf design that explicitly enables efficient ordered iteration and range queries.

  3. 3
    Step 3

    This contradicts that B+ trees support efficient searching (root-to-leaf descent) for point lookups.

  4. 4
    Step 4

    This matches both: logarithmic-height searching for point lookups and linked leaves for efficient range/ordered scans.

  5. 5
    Step 5

    This contradicts that ordered iteration is made “simpler and more efficient” due to linked leaves.

Why linked leaves matter

For range queries, B+ trees can avoid restarting from the root for every next key: after one O(log⁡n)O(\log n) search to the first leaf, the leaf-level linked list supports a forward scan.2

Footnotes

  1. B+ tree - Wikipedia - Describes linked leaves and how it simplifies efficient range queries/ordered iteration. ↩

  2. B+ Tree Visualizer | Linked-Leaf Multi-Way Search Tree - States range queries: O(log⁡n)O(\log n) to find start key, then linear scan along leaf chain; summarizes O(log⁡n+k)O(\log n + k). ↩

Common confusion: B+ tree vs B-tree

A B+ tree’s defining advantage for scans comes from where data lives and how leaves are connected. In contrast, a B-tree can store data at internal nodes and does not provide the same linked-leaf scan path, so range iteration is typically less efficient.2

Footnotes

  1. B+ tree - Wikipedia - Describes linked leaves and how it simplifies efficient range queries/ordered iteration. ↩

  2. B+ Tree Visualizer | Linked-Leaf Multi-Way Search Tree - States range queries: O(log⁡n)O(\log n) to find start key, then linear scan along leaf chain; summarizes O(log⁡n+k)O(\log n + k). ↩

Conclusion: the correct choice

Given B+ trees support:

  • rapid point lookups (random access via O(log⁡n)O(\log n) descent), and
  • rapid ordered iteration / range scans (sequential access via linked leaves),

the correct option is:

✅ (iii) B+ tree allows rapid random access as well as rapid sequential access

Memory I/O intuition across workloads

Root-to-leaf descent

Point lookup (random)

Use index keys in internal nodes to reach the correct leaf in O(log⁡n)O(\log n)."

Scan leaf chain

Range query (sequential)

After locating the first matching leaf (O(log⁡n)O(\log n)), traverse linked leaves to collect results."

Linear in output size

Result processing

If kk keys match, scanning/reporting costs scale with kk (often summarized as O(log⁡n+k)O(\log n + k))."

Access pattern fit for B+ trees (conceptual)

Qualitative match to the two access patterns referenced in the options

Knowledge Check

Question 1 of 4
Q1Single choice

Which statement about B+ trees is true?

Explore Related Topics

1

Closure Properties of Turing-Language Classes: Identifying False Statements

2

B-Trees for Database Indexing: Structure, Properties, and Operations

3

Binary Search Complexity: Why the Correct Choice is $O(\log n)$

Browse all research articles