Why does search in a B-tree work faster than linear search?

Search in a B-tree is faster due to its structure, which minimizes the number of comparisons and disk operations.

• Logarithmic complexity: B-trees have logarithmic search time complexity, O(log N), where N is the number of elements. This is achieved by representing data as a balanced tree with multiple keys in each node.
• Branching: Each node can contain multiple keys and child pointers. During search, we compare the sought key with the keys in the current node, determining the correct child node to proceed to. This significantly reduces the number of nodes that need to be visited.
• Optimization for disk access: The size of nodes in a B-tree is usually chosen to match the disk block size. This allows reading a large amount of data into memory at once when loading a node, minimizing the number of slow disk input-output operations. Linear search, on the other hand, requires sequentially reading each element.

In contrast, linear search has linear complexity O(N), requiring up to N comparisons in the worst case.