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. 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 records in the order they are inserted. For example, a heapUnordered storage typically stores the records in the order they are inserted. Such storage offers good insertion efficiency ( O ( 1 ) {displaystyle Oleft(1 ight)} ), but inefficient retrieval times ( O ( n ) {displaystyle Oleft(n ight)} ). Typically these retrieval times are better, however, as most databases use indexes on the primary keys, resulting in retrieval times of O ( log ⁡ n ) {displaystyle Oleft(log n ight)} or O ( 1 ) {displaystyle Oleft(1 ight)} for keys that are the same as the database row offsets within the storage system. Ordered storage typically stores the records in order and may have to rearrange or increase the file size when a new record is inserted, resulting in lower insertion efficiency. However, ordered storage provides more efficient retrieval as the records are pre-sorted, resulting in a complexity of O ( log ⁡ n ) {displaystyle Oleft(log n ight)} . Heap files are lists of unordered records of variable size. Although sharing a similar name, heap files are widely different from in-memory heaps. In-memory heaps are ordered, as opposed to heap files.