What is the approximate complexity of searching data by index in a database?

The complexity of searching by index in a B-tree or B+ tree (the most common types of indexes) is approximately O(log N), where N is the number of records in the table.

This logarithmic complexity is due to the tree-like structure of the index. At each level of the tree, we choose the branch containing the desired range of keys, significantly reducing the search space. The height of the tree, and consequently the number of steps to find, grows logarithmically with the number of records.

Example: in a tree with 1 million records, if each node can contain 100 pointers, the height of the tree will be approximately log₁₀₀(1,000,000) = 3. This means that to find a record, it will take about 3 nodes to be traversed.