General Search Tree

DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).

General Search Tree

Not every search tree is binary — sometimes a node can have many children.

A general search tree allows any number of children per node (not restricted to 2 like a BST) — used when the underlying problem naturally branches into more than two possibilities, such as searching through a game's possible move sequences.

💡 One-liner: "Give a real scenario where a general (non-binary) search tree fits naturally." → Modeling all possible moves in a board game like chess, where each position can branch into many possible next moves, not just two.

Why more children can mean fewer levels

A binary tree with n nodes has a height of about log₂n. Let each node hold more children and the tree gets shallower for the same number of nodes — with m children per node the height is roughly log_mn.

That sounds like a marginal gain until you ask what each level costs. In a database index living on disk, one level down means one disk read — thousands of times slower than any comparison. Halving the number of levels roughly halves the query time, so index structures deliberately use very high branching factors, packing hundreds of keys into a node sized to match one disk block.

💡 This is the reasoning behind B-trees and B+ trees, which underpin essentially every relational database index. They are general search trees chosen for exactly this reason: fewer levels means fewer disk reads, and disk reads are what dominate the cost.

Where the branching comes from the problem

Sometimes the arity is not a design choice but the shape of the problem. A game tree branches into however many legal moves exist from a position; a file system branches into however many entries a directory holds; a decision tree branches into however many outcomes a test has. Forcing these into a binary structure would add levels without adding information.

Syllabus points

General search tree concept

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.