B+ Trees and Hash Indexing

1. B+ Trees 🌳

👉 Think of it like a sorted bookshelf with an index guide.

  • Definition: Self-balancing tree structure for indexing.
  • Keys stored in order → Sorted.
  • Internal Nodes: Guide (like index pages).
  • Leaf Nodes: Store actual data + linked together for easy scanning.
  • Height Balanced: All leaves at the same level.

Advantages:

  • Search, insert, delete = O(log N).
  • ✅ Supports range queries (e.g., 10 < ID < 50).
  • ✅ Easy sequential access (leaves linked).

Use: MySQL, PostgreSQL, file systems.

2. Hash Indexing #️⃣

👉 Think of it like buckets in a cupboard, found using a formula.

  • Definition: Uses hash function → maps a key to a bucket.
  • Best for exact match (e.g., ID = 123).

Structure:

  • Hash Function: Calculates position.
  • Buckets: Store data (or pointers).

Advantages:

  • Super fast lookup → O(1) (best case).
  • Simple.

Limitations:

  • ❌ No range queries (unordered).
  • ❌ Collisions possible (two keys → same bucket).

Collision Handling:

  • Chaining: Keep a linked list in the bucket.
  • Open Addressing: Find another free bucket.

Use: Hash tables (Python dicts, DB indexes).

3. Quick Comparison ⚔️

FeatureB+ Trees 🌳Hash Indexing #️⃣
Query Type✅ Range + exact✅ Exact only
SpeedO(log N)O(1) best case
OrderSortedUnordered
StructureHierarchical (tree)Buckets (flat)
Use CaseDatabases, filesystemsEquality lookups

4. Memory Tricks 🧠

  • B+ Tree = “Tree + Sorted” → good for ranges.
  • Hash = “Buckets + Hash Function” → good for exact matches.

MCQ

Topic 1: B+ Trees

  1. What is a key feature of a B+ Tree compared to a binary search tree?
    A. Keys are unsorted in leaf nodes.
    B. Data is stored only in internal nodes.
    C. All leaf nodes are at the same level.
    D. No balancing is required.
    Answer: C
  2. Which of the following operations in a B+ Tree has a time complexity of O(log N)?
    A. Search
    B. Insert
    C. Delete
    D. All of the above
    Answer: D
  3. In a B+ Tree, where are the actual data or records stored?
    A. In the root node
    B. In the internal nodes
    C. In the leaf nodes
    D. In a separate hash table
    Answer: C
  4. Why are B+ Trees suitable for database indexing?
    A. They allow sequential access to records.
    B. They have no height balancing.
    C. They store duplicate keys in internal nodes.
    D. They require less memory.
    Answer: A
  5. Which of the following is true for B+ Trees?
    A. Internal nodes contain pointers to data records.
    B. Leaf nodes are not linked.
    C. Internal nodes store only keys and child pointers.
    D. It is an unbalanced data structure.
    Answer: C
  6. What happens to a B+ Tree when an insertion causes a node to overflow?
    A. The node is deleted.
    B. The node is split, and the median key is promoted.
    C. The tree becomes unbalanced.
    D. All keys are shuffled.
    Answer: B

Topic 2: Hash Indexing

  1. What is the primary use of hash indexing in databases?
    A. Range queries
    B. Exact match queries
    C. Sorting data
    D. Managing transactions
    Answer: B
  2. Which of the following is an example of a hash function?
    A. Binary search
    B. Modulo operation (key % number of buckets)
    C. Depth-first traversal
    D. Exponential function
    Answer: B
  3. What is the main problem addressed by collision handling in hash indexing?
    A. Storing large datasets
    B. Keys mapping to the same bucket
    C. Searching within a bucket
    D. Sorting keys within buckets
    Answer: B
  4. Which method is commonly used to handle collisions in hash indexing?
    A. Balancing
    B. Chaining
    C. Promotion
    D. Traversal
    Answer: B
  5. What is the worst-case time complexity for searching in hash indexing?
    A. O(1)
    B. O(log N)
    C. O(N)
    D. O(N log N)
    Answer: C
  6. Which of the following is a limitation of hash indexing?
    A. It requires more storage than B+ Trees.
    B. It does not support range queries.
    C. It cannot handle duplicate keys.
    D. It cannot be implemented in databases.
    Answer: B

Topic 3: Comparison and Applications

  1. Which data structure is better for range queries in databases?
    A. B+ Tree
    B. Hash Table
    C. Binary Search Tree
    D. Graph
    Answer: A
  2. Why are hash indexes not used for range queries?
    A. They are too slow for exact match queries.
    B. They do not store data sequentially.
    C. They use too much memory.
    D. They require too much computation.
    Answer: B
  3. In which scenario would you prefer hash indexing over a B+ Tree?
    A. Searching for all values in a range
    B. Sorting data in a database
    C. Performing exact match queries
    D. Storing hierarchical data
    Answer: C
  4. What is a common use case for B+ Trees?
    A. Equality-based lookups
    B. Maintaining a cache
    C. File system indexing
    D. Graph traversal
    Answer: C
  5. If you need to store a large number of unique keys with frequent insertions and deletions, which indexing method should you choose?
    A. Hash Indexing
    B. B+ Tree
    C. AVL Tree
    D. Binary Heap
    Answer: B
  6. Which of the following is an advantage of B+ Trees over hash indexing?
    A. Faster exact match queries
    B. Ability to handle range queries efficiently
    C. Lower memory usage
    D. Simpler implementation
    Answer: B

Topic 4: Practical Examples

  1. What would be the output of a hash function key % 5 for key = 12?
    A. 0
    B. 2
    C. 5
    D. 7
    Answer: B
  2. If a B+ Tree has a branching factor of 4 and contains 3 levels (root, internal, and leaf), what is the maximum number of keys it can store?
    A. 4
    B. 64
    C. 80
    D. 85
    Answer: C
  3. Given a hash table with 10 buckets and a key-value pair (25, “A”), where would the key 25 be stored if the hash function is key % 10?
    A. Bucket 0
    B. Bucket 2
    C. Bucket 5
    D. Bucket 10
    Answer: C