Table Structures


A table structure is a scheme for organizing rows in blocks on storage media.

  • row-oriented storage performs better than column-oriented storage for most transactional databases
    • thus relational databases commonly use row-oriented storage
  • 4 common table structures:
    • Heap table
    • Sorted table
    • Hash table
    • Table cluster
  • each table in a database can have a different structure
  • databases have a default structure
    • administrators can override the default to optimize performance for specific queries

Heap Table

A heap table imposes no order on rows.

  • database maintains a list of blocks assigned to the table along with the address of the first available space for inserts
  • if all blocks are full,
    • database allocates a new block and inserts rows in the new block
  • when a row is deleted,
    • the space occupied by the row is marked as free
  • free space is tracked as a linked list
    • inserts are stored in the first space in the list
    • the head of the list is set to the next space
  • optimizes insert operations
  • particularly fast for bulk load of many rows
    • since rows are stored in load order
  • not optimal for queries that read rows in a specific order
    • since rows are scattered randomly across storage media

Heap Table

Sorted Table

In a sorted table, the database designer identifies a sort column that determines physical row order.

  • sort column is usually the primary key
    • but can be a non-key column or group of columns
  • rows are assigned to blocks according to the value of the sort column
    • each block contains all rows with values in a given range
    • within each block, rows are located in order of sort columns
  • sorted tables are optimal for queries that read data in order of the sort column
    • e.g.,
      • JOIN on the sort column
      • SELECT with range of sort column values in the WHERE clause
      • SELECT with ORDER BY the sort column
  • maintaining sort order of rows within each block can be slow
    • when a new row is inserted, or when the sort column is updated,
      • free space may not be available in the correct location
  • to maintain correct order efficiently,
    • databases maintain pointers to the next row within each block
    • inserts and updates change two address values rather than move entire rows
  • when an attempt is made to insert a row into a full block, the block splits in two
    • database moves half the rows from the initial block to a new block
      • creating space for the insert
  • sorted tables are optimized for read queries
    • at the expense of insert and update operations

Hash Table

In a hash table, rows are assigned to buckets.

  • bucket is a block or group of blocks containing rows
    • initially, each bucket has one block
    • as a table grows, some buckets fill up with rows and the database allocates additional blocks
    • new blocks are linked to the initial block
    • bucket becomes a chain of linked blocks
  • bucket containing each row is determined by a hash function and hash key
    • hash key is a column or group of columns
      • usually the primary key
    • hash function computes the bucket containing the row from the hash key
      • designed to:
        • scramble row locations
        • evenly distribute rows across buckets
  • modulo function is a simple hash function with 4 steps:
    1. convert the hash key by interpreting the key’s bits as an integer value
    2. divide the integer by the number of buckets
    3. interpret the division remainder as the bucket number
    4. convert the bucket number to the physical address of the block containing the row
  • deep buckets with many linked blocks are inefficient
    • to avoid, database may use a dynamic hash function
      • automatically allocates more blocks to the table, creates additional buckets, and distributes rows across all buckets
    • more buckets = fewer rows per bucket = buckets with fewer linked blocks
  • optimal for
    • inserts and deletes of individual rows
      • because row location is quickly determined by the hash key
    • selecting a single row when hash key value is specified in the where clause
  • slow for queries that select many rows with a range of values
    • because rows are randomly distributed across many blocks

Table Clusters

Table clusters interleave rows of two or more tables in the same storage area.

  • aka multi-tables
  • have a cluster key
    • a column that is available in all interleaved tables
    • determines the order in which rows are interleaved
    • rows with same cluster key value are stored together
    • is usually the primary key of one table and the foreign key of another
  • optimal when joining interleaved tables on the cluster key
    • since physical row location is not the same as output order
  • perform poorly for:
    • join columns other than cluster key
      • in a join on a column that is not the cluster key, physical row location is not the same as output order, so the join is slow
    • read multiple rows of a single table
      • table clusters spread each table across more blocks than other structures
      • reading multiple rows may access more blocks
    • update cluster key
      • rows may move to different blocks when the cluster key changes
  • not commonly used