Database_storage_structures

Database tables/indexes are typically stored in memory or on hard disk in one of many forms, ordered/unordered Flat files, ISAM, Heaps, Hash buckets or B+ Trees. These have various advantages and disadvantages discussed in this topic. The most commonly used are B+trees and ISAM.

Methods

Flat files

Main article: Flat file database

A flat file database describes any of various means to encode a data model (most commonly a table) as a plain text file.

Unordered

This short section requires expansion.

Unordered storage typically stores the records in the order they are inserted, while having good insertion efficiency, it may seem that it would have inefficient retrieval times, but this is usually never the case as most databases use indexes on the primary keys, resulting in efficient retrieval times.

Ordered

This short section requires expansion.

Ordered or Linked list storage typically stores the records in order and may have to rearrange or increase the file size in the case a record is inserted, this is very inefficient. However is better for retrieval as the records are pre-sorted (Complexity O(log(n))).

Structured files

Heaps

• simplest and most basic method
  • insert efficient, records added at end of file – ‘chronological’ order
  • retrieval inefficient as searching has to be linear
  • deletion – deleted records marked

requires periodic reorganization if file is very volatile

• advantages
  • good for bulk loading data
  • good for relatively small relations as indexing overheads are avoided
  • good when retrievals involve large proportion of records
• disadvantages
  • not efficient for selective retrieval using key values, especially if large
  • sorting may be time-consuming
• not suitable for ‘volatile’ tables

Hash buckets

• Hash functions calculate the address of the page in which the record is to be stored based on one or more fields in the record
  • Hashing functions chosen to ensure that addresses are spread evenly across the address space
  • ‘occupancy’ is generally 40% – 60% of total file size
  • unique address not guaranteed so collision detection and collision resolution mechanisms are required
• open addressing
• chained/unchained overflow
• pros and cons
  • efficient for exact matches on key field
  • not suitable for range retrieval, which requires sequential storage
  • calculates where the record is stored based on fields in the record
  • hash functions ensure even spread of data
  • collisions are possible, so collision detection and restoration is required

B+ trees

These are the most used in practice.

• the time taken to access any tuple is the same because same number of nodes searched
• index is a full index so data file does not have to be ordered
• Pros and cons
  • versatile data structure – sequential as well as random access
  • access is fast
  • supports exact, range, part key and pattern matches efficiently
  • ‘volatile’ files are handled efficiently because index is dynamic – expands and contracts as table grows and shrinks
  • less well suited to relatively stable files – in this case, ISAM is more efficient

ISAM

This short section requires expansion.

See also

• ISAM
• B+tree
• Flat file database
• Hash tables
• Heaps

This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia