Miks on B-puu otsing kiirem kui lineaarne otsing?

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 a 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 pointers to children. During search, we compare the sought key with the keys in the current node, determining the correct child node to continue. This significantly reduces the number of nodes to visit.
• Optimization for disk access: The size of nodes in a B-tree is usually chosen to match the size of a disk block. This allows loading a node into memory at once, reading large volumes of data and minimizing slow disk input/output operations. Linear search, on the other hand, requires sequentially reading each element.