Why is an array accessible in O(1)

Why is a database key-value lookup O(log n)?

Databases are made to store hugh and complex datastructures permanently. To do that, the storage of data is decoupled from the index. The index is usually maintained in an balanced binary index tree. The lookup time of an index is therefore the path of an tree which has the time of O(log n).

Why is an array faster then database?

An array is stored in memory. To store an array in memory, you need to store the position in memory where the array starts, and then store for each index a space. The values of the array can need different sizes of space in memory, so only the reference to the value will be stored, which all take the same amount of space. For example, if array starts at byte 20, and each reference is 4 byte, then you can access element 100 of your array by looking from byte 20 + (1004) to byte 20 + (1014). Therefore you can actually access any key at O(1).

Why are databases store index in a tree?

A tree for indexes offers many features, like efficient range queries, support for multiple indexes, build-in data sorting. Having the indexes in a tree is causing the O(logn) lookup time.

If the ID is an auto-increment integer, it is possible to do a lookup in O(1) time using an array or a hash table, provided that the IDs are consecutive and there are no gaps in the sequence. In this case, the ID can be used as an index to directly access the corresponding data record. However, in many real-world scenarios, the IDs are not necessarily consecutive, and there may be gaps in the sequence due to data deletions or because of failed transactions. In this case, using an array or a hash table for lookup may not be practical, since it would require allocating an array large enough to accommodate all possible IDs, even if many of them are not used.

While B-trees and other indexing mechanisms may not provide the same level of performance as an array or a hash table for consecutive IDs, they are more flexible and can handle a wider range of data models and access patterns.