Database storage structures

Database tables and indexes may be stored on disk in one of a number of forms, including ordered/unordered flat files, ISAM, heap files, hash buckets, or B+ trees. Each form has its own particular advantages and disadvantages. The most commonly used forms are B+ trees and ISAM. Such forms or structures are one aspect of the overall schema used by a database engine to store information.

Unordered storage typically stores the records in the order they are inserted. Such storage offers good insertion efficiency (${\displaystyle O\left(1\right)}$), but inefficient retrieval times (${\displaystyle O\left(n\right)}$). Typically these retrieval times are better, however, as most databases use indexes on the primary keys, resulting in retrieval times of ${\displaystyle O\left(\log n\right)}$ or ${\displaystyle O\left(1\right)}$ for keys that are the same as the database row offsets within the storage system.

...
Wikipedia