Searching an entry in a B(+)-Tree data structure has an average time complexity of O(log n); more precisely, log_b n = log_2 n / log_2 b where b is the branching factor of the B(+)-Tree and n is the number of indexed rows. Because b is typically between several hundred and several thousand, B(+)-Trees are very shallow structures, and few disk-seeks are required to locate records. With 8.87 million rows and a branching factor of 1000, 2.3 disk seeks are needed on average. This capability comes at a cost: additional disk and memory overheads, higher insertion costs when adding new rows to the table and entries to the index, and sometimes rebalancing of the B-Tree.
: The formula shows how to convert the logarithm base from bb to 2. This is useful because logarithms with different bases are proportional to each other.
Disk Seeks: In the context of databases, a disk seek is the time it takes to move the read/write head of a disk drive to the location where data is stored. Fewer disk seeks mean faster data retrieval. With a branching factor of 1000 and 8.87 million rows, the average number of disk seeks required is approximately 2.3. This low number of disk seeks is due to the shallow nature of the B(+)-Tree.