D426 Chapter 5 — Indexes: Table Structures & Single-Level Indexes

WGU D426 zyBooks Ch 5, sections 5.1–5.2 (5.2 Single-level indexes transcribed from the live zyBook because it didn't print). Key terms verbatim plus concept, comparison and scenario cards. Not official WGU or zyBooks material.

Table structure

A table structure is a scheme for organizing rows in blocks on storage media. | Context: row-oriented storage performs better than column-oriented storage for most transactional databases, so relational databases commonly use row-oriented storage. (§5.1)

Heap table

In a heap table, no order is imposed on rows. The 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, the database allocates a new block and inserts rows in the new block. (§5.1)

Free space pointer

In a heap table, the database maintains a pointer to free space, which indicates the location of the next insert. (§5.1)

Sorted table

In a sorted table, the database designer identifies a sort column that determines physical row order. 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 column values. (§5.1)

Sort column

In a sorted table, the database designer identifies a sort column that determines physical row order. The sort column is usually the primary key but can be a non-key column or group of columns. (§5.1)

Hash table

In a hash table, rows are assigned to buckets. | The bucket containing each row is determined by a hash function and a hash key. (§5.1)

Bucket

A bucket is a block or group of blocks containing rows. Initially, each bucket has one block. As a table grows, some buckets eventually fill up with rows, and the database allocates additional blocks. New blocks are linked to the initial block, and the bucket becomes a chain of linked blocks. (§5.1)

Hash key

The hash key is a column or group of columns, usually the primary key. (§5.1)

Hash function

The hash function computes the bucket containing the row from the hash key. | Hash functions are designed to scramble row locations and evenly distribute rows across blocks. (§5.1)

Modulo function

The modulo function is a simple hash function with four 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. (§5.1)

Deep buckets

As tables grow, a fixed hash function allocates more rows to each bucket, creating deep buckets consisting of long chains of linked blocks. Deep buckets are inefficient since a query may read several blocks to access a single row. (§5.1)

Dynamic hash function

A dynamic hash function automatically allocates more blocks to the table, creates additional buckets, and distributes rows across all buckets. | To avoid deep buckets, databases may use dynamic hash functions. (§5.1)

Table clusters

Table clusters, also called multi-tables, interleave rows of two or more tables in the same storage area. (§5.1)

Multi-tables

Another name for table clusters: Table clusters, also called multi-tables, interleave rows of two or more tables in the same storage area. (§5.1)

Cluster key

Table clusters have a cluster key, a column that is available in all interleaved tables. The cluster key determines the order in which rows are interleaved. Rows with the same cluster key value are stored together. Usually the cluster key is the primary key of one table and the corresponding foreign key of another. (§5.1)

The four table structures: how each orders, inserts, and finds rows

1) Heap table: no order; inserts go to the first available free space; rows are scattered, so reading them in a specific order is slow. | 2) Sorted table: rows in sort column order, each block holding a range of values; next-row pointers keep the order on inserts; reads in sort column order are fast. | 3) Hash table: a hash function computes each row's bucket from the hash key; single-row inserts, deletes, and lookups by hash key are fast, ranges are slow. | 4) Table cluster: rows of two or more tables interleaved in cluster key order; joins on the cluster key are fast. | Each table can have a different structure: databases assign a default, and database administrators can override it to optimize performance for specific queries. (§5.1)

Heap table: what happens to the free space list on a delete, and on an insert?

Delete: the row's space is marked as free, the free space pointer moves to that space, and the space is linked to the previous first free space (at first, the free space at the end of the table). Free space is typically tracked this way, as a linked list. | Insert: the row is stored in the first space in the list, and the head of the list is set to the next space. | If all blocks are full, the database allocates a new block and inserts rows there. (§5.1)

Sorted table: how does it keep sort order on inserts and updates, and what happens when a block is full?

An insert, or an update to a row's sort column, may find no free space in the correct location, and moving rows to make room is inefficient. So databases maintain pointers to the next row within each block; inserts and updates change two address values rather than move entire rows. | Full block: the block splits in two. The database moves half the rows from the initial block to a new block, creating space for the insert, so both blocks end up about half full. (§5.1)

Modulo hash function: which bucket gets hash key 2013 when the hash function is modulo 8?

Bucket 5. Interpret the key as an integer (2013), divide by the number of buckets (2013 ÷ 8 = 251 remainder 5), and use the remainder as the bucket number; modulo 8 gives buckets 0–7. The database then converts bucket 5 to the physical address of the block containing the row. | Shortcut for modulo 10: the bucket is the key's last digit, so hash key 3417 goes to bucket 7. (§5.1)

Table clusters: when are they optimal, and when do they perform poorly?

Optimal: joining the interleaved tables on the cluster key, since physical row location is the same as output order. | Poor: 1) a join on columns other than the cluster key (physical row location isn't output order, so the join is slow); 2) reading multiple rows of a single table (each table is spread across more blocks than in other structures, so more blocks may be read); 3) updating the cluster key (rows may move to different blocks). | Since they're not optimal for many queries, table clusters are not commonly used. (§5.1)

Heap table vs sorted table

Heap: no order is imposed on rows. Optimizes inserts and is particularly fast for bulk loads, since rows are stored in load order; not optimal for reading rows in a specific order, such as a range of primary key values, because rows are scattered. | Sorted: a sort column determines physical row order. Optimal for reading in sort column order (JOIN on it, a range of its values in WHERE, ORDER BY it), at the expense of inserts and updates. Reads are more frequent than updates and inserts in many databases, so sorted tables are often used, usually with the primary key as the sort column. (§5.1)

Hash table vs sorted table

Hash: a hash function scrambles rows across buckets, and a row's location is quickly determined from its hash key. Optimal for inserting or deleting individual rows and for selecting a single row with the hash key value in WHERE; slow for selecting many rows with a range of values, since they're spread randomly across many blocks. | Sorted: rows sit in sort column order, each block holding a range of values. Optimal for range reads, ORDER BY, and JOIN on the sort column; inserts and updates are the costly part. (§5.1)

Sort column vs hash key vs cluster key

Sort column (sorted table): determines physical row order; usually the primary key but can be a non-key column or group of columns. | Hash key (hash table): a column or group of columns from which the hash function computes each row's bucket; usually the primary key. | Cluster key (table cluster): a column available in all interleaved tables; it determines the order rows are interleaved and keeps rows with the same value together; usually one table's primary key and the other table's corresponding foreign key. (§5.1)

Full block in a sorted table vs full bucket in a hash table

Sorted table: the block splits in two, and the database moves half the rows from the initial block to a new block, creating space for the insert. | Hash table: the database allocates another block and links it to the bucket's initial block, so the bucket becomes a chain of linked blocks. In the book's animation, the rows already stored stay in block 1 and the new row goes in block 2. (§5.1)

Fixed hash function vs dynamic hash function as a table grows

Fixed: allocates more rows to each bucket as the table grows, so buckets fill and become deep buckets (long chains of linked blocks), where a query may read several blocks to access a single row. | Dynamic: automatically allocates more blocks to the table, creates additional buckets, and distributes rows across all buckets; with more buckets, fewer rows are assigned to each bucket and, on average, buckets contain fewer linked blocks. (§5.1)

Scenario: A video-streaming service bulk-loads millions of PlaybackEvent rows every night and almost never reads them back in any particular order. Which table structure fits best?

Heap table: heap tables optimize inserts and are particularly fast for bulk load of many rows, since rows are stored in load order. Their weakness, queries that read rows in a specific order, doesn't matter for this workload. (§5.1)

Scenario: A clinic's check-in kiosk inserts, deletes, and looks up one Patient row at a time, always by a single PatientID value in the WHERE clause; reports over ranges of PatientID are rare. Which structure fits best, and what is the hash key?

A hash table with PatientID as the hash key. Row location is quickly determined from the hash key, so inserts and deletes of individual rows, and selecting a single row with the hash key value in WHERE, are optimal. Range queries would be slow because rows are randomly distributed across many blocks, but they're rare here. (§5.1)

Scenario: A library's Loan table is read mostly by reports that list loans due between two dates, ordered by DueDate; new loans are added far less often than the reports run. Which structure fits best, and on which column?

A sorted table with DueDate as the sort column. Sorted tables are optimal for SELECT with a range of sort column values in the WHERE clause and for SELECT with ORDER BY the sort column. The sort column is usually the primary key but can be a non-key column, as here. Inserts cost more, but reads dominate this workload. (§5.1)

Scenario: A game studio's Guild and Member tables are almost always queried together by joining on GuildID (Guild's primary key, Member's foreign key). Which structure makes that join fastest, and what's the catch?

A table cluster with GuildID as the cluster key: rows with the same GuildID are stored together, so physical row location matches the join's output order. The catch: joins on other columns, reading many rows of just one table, and updating GuildID all perform poorly, which is why table clusters are not commonly used. (§5.1)

Scenario: A parking garage logs entries in a heap table whose free space pointer points to the free space at the end of the table. The row for ticket T-220 is deleted, then the row for ticket T-105, which sits earlier in the table. Where do the next three inserted rows go?

1) T-105's old space: the last delete moved the free space pointer there. | 2) T-220's old space: T-105's space is linked to it. | 3) The free space at the end of the table. | Each delete moves the pointer to the freed space and links that space to the previous first free space; each insert takes the first space in the list. (§5.1)

Single-level index

A single-level index is a file containing column values, along with pointers to rows containing the column value. The pointer identifies the block containing the row. In some indexes, the pointer also identifies the exact location of the row within the block. | Single-level indexes are normally sorted on the column value. If an indexed column is unique, the index has one entry for each column value; if not unique, the index may have multiple entries for some column values, or one entry for each column value, followed by multiple pointers. | Indexes are created by database designers with the CREATE INDEX command. (§5.2)

Multi-column index

An index is usually defined on a single column, but an index can be defined on multiple columns. In a multi-column index, each index entry is a composite of values from all indexed columns. In all other respects, multi-column indexes behave exactly like indexes on a single column. (§5.2)

Table scan

A table scan is a database operation that reads table blocks directly, without accessing an index. | The database performs a table scan when hit ratio is high, and must perform one when the WHERE clause does not contain an indexed column. (§5.2)

Index scan

An index scan is a database operation that reads index blocks sequentially, in order to locate the needed table blocks. | Used when hit ratio is low and the WHERE clause contains an indexed column. (§5.2)

Hit ratio (filter factor, selectivity)

Hit ratio, also called filter factor or selectivity, is the percentage of table rows selected by a query. | When a SELECT query is executed, the database examines the WHERE clause and estimates hit ratio: high hit ratio → table scan; low hit ratio → index scan, if the WHERE clause contains an indexed column. (§5.2)

Binary search

In a binary search, the database repeatedly splits the index in two until it finds the entry containing the search value. Steps: | 1) Compare the search value to an entry in the middle of the index. | 2) If the search value is less than the entry value, the search value is in the first half of the index; if not, it is in the second half. | 3) Compare the search value to the entry in the middle of the selected half, narrowing the search to one quarter of the index. | 4) Continue in this manner until finding the index block containing the search value. | Works on a sorted single-level index; used because index scans are too slow in many cases. (§5.2)

Primary index (clustering index)

A primary index, also called a clustering index, is an index on a sort column. | A sorted table can have only one sort column, and therefore only one primary index. Usually, the primary index is on the primary key column(s); in some database systems, the primary index may be created on any column. Primary indexes are usually sparse. (§5.2)

Secondary index (nonclustering index)

A secondary index, also called a nonclustering index, is an index that is not on the sort column. | Tables can have many secondary indexes. All indexes of a heap or hash table are secondary, since heap and hash tables have no sort column. Secondary indexes are always dense. (§5.2)

Dense index

A dense index contains an entry for every table row. | Secondary indexes are on non-sort columns and therefore are always dense. (§5.2)

Sparse index

A sparse index contains an entry for every table block. | When a table is sorted on an index column, the index may be sparse: a value with no index entry is in the block that sort order points to. Primary indexes are on sort columns and usually sparse. (§5.2)

Query processing: how does the database choose between a table scan and an index scan?

The database examines the WHERE clause and estimates hit ratio. | High hit ratio: table scan. | Low hit ratio: the query needs only a few table blocks, so a table scan would be inefficient. Instead, the database 1) looks for an indexed column in the WHERE clause, 2) scans the index, 3) finds values that match the WHERE clause, 4) reads the corresponding table blocks. | If the WHERE clause does not contain an indexed column, the database must perform a table scan. (§5.2)

Dense index: what happens on an insert, a delete, and an update?

Insert: a new index entry is created and must be placed in the correct index block, since single-level indexes are sorted. If this block is full, the block splits in two to create space for the new entry. | Delete: the row's index entry must be deleted. Physically removing it requires moving all subsequent entries, which is slow, so index entries are marked as 'deleted'. Periodically, the database may reorganize the index to remove deleted entries and compress the index. | Update: an update to a column that is not indexed does not affect the index. An update to an indexed column is like a delete followed by an insert: the entry for the initial value is deleted and an entry for the updated value is inserted. | Sparse index: entries are inserted or deleted when blocks split or merge, which happens less often than row inserts and deletes; aside from frequency, the behavior is similar. (§5.2)

Why are sparse indexes fast? (the book's 10-million-row example)

Sparse indexes have fewer entries and occupy fewer blocks than dense indexes. | Example: a table has 10 million rows of 100 bytes, table and index blocks are 4 KB, and each index entry is 10 bytes. The table occupies 250,000 blocks (10 million rows × 100 bytes / 4 KB). A sparse index needs 250,000 entries (one per table block) and occupies 625 blocks (250,000 entries × 10 bytes / 4 KB), so it can easily be retained in main memory. The arithmetic treats 4 KB as 4,000 bytes. | Since primary indexes are usually sparse and sparse indexes are fast, database designers usually create a primary index on the primary key of large tables. (§5.2)

Terminology: what do primary index and clustering index mean?

The meanings of primary index and clustering index vary. In some database systems, primary and clustering indexes are indexes on unique and non-unique sort columns, respectively. | In this material, the terms are synonymous and refer to an index on any sort column. (§5.2)

Table scan vs index scan

Table scan: reads table blocks directly, without accessing an index. Chosen when hit ratio is high; required when the WHERE clause has no indexed column. | Index scan: reads index blocks sequentially to locate the needed table blocks. Chosen when hit ratio is low and the WHERE clause has an indexed column. | Index scans are much faster: a column value and pointer occupy less space than an entire row, so an index requires fewer blocks than a table, and some indexes are small enough to reside in main memory. (§5.2)

Primary index vs secondary index

Primary (clustering): an index on the sort column. Only one per table, since a sorted table has only one sort column; usually on the primary key; usually sparse. | Secondary (nonclustering): an index not on the sort column. A table can have many, and they are always dense. Every index of a heap or hash table is secondary, since those tables have no sort column. (§5.2)

Dense index vs sparse index

Dense: an entry for every table row. Secondary indexes are always dense. | Sparse: an entry for every table block. Possible when the table is sorted on the index column; primary indexes are usually sparse. | Sparse indexes are much faster, since they have fewer entries and occupy fewer blocks. Their entries change only when blocks split or merge. (§5.2)

Clustering index vs cluster key

Clustering index: another name for a primary index, an index on a sort column. | Cluster key: a column available in all tables interleaved in a table cluster; it determines the order in which rows are interleaved. | A clustering index is not the same as a cluster key. A cluster key refers to a table cluster storage structure and is not an index. (§5.1, §5.2)

Sorted index vs index on a sorted table

Single-level indexes are normally sorted on the column value, whatever the table's structure. A sorted index is not the same as an index on a sorted table. | Ex: An index on a heap table is a sorted index on an unsorted table. Since heap tables have no sort column, that index is also secondary and dense. (§5.2)

Scenario: A camping outfitter's Rental table has an index on CustomerID only. How does the database run (1) SELECT * FROM Rental WHERE CustomerID = 3307; (a few rows) and (2) SELECT * FROM Rental WHERE RentalDate = '2026-11-02';?

1) Index scan: the hit ratio is low and the WHERE clause contains an indexed column, so the database scans the CustomerID index, finds the matching values, and reads only the corresponding table blocks. | 2) Table scan: the WHERE clause does not contain an indexed column, so the database must perform a table scan. (§5.2)

Scenario: An urgent-care center's Visit table is sorted on VisitID and has indexes on VisitID and DoctorID; its LabResult table is a heap table with an index on PatientID. Classify each index: primary or secondary, dense or sparse.

VisitID index: primary (clustering), since it is on the sort column; it may be, and usually is, sparse. | DoctorID index: secondary (nonclustering), since it is not on the sort column, so it is dense. | PatientID index on LabResult: secondary and dense, since a heap table has no sort column. (§5.2)

Scenario: A warehouse's Shipment table is sorted on ShipmentID and holds 2,000,000 rows of 200 bytes. Table and index blocks are 8,000 bytes, and each index entry is 16 bytes. How many blocks do the table, a dense index, and a sparse index on ShipmentID occupy?

Table: 2,000,000 rows × 200 bytes / 8,000 bytes per block = 50,000 blocks. | Dense index (one entry per row): 2,000,000 entries × 16 bytes / 8,000 bytes = 4,000 blocks. | Sparse index (one entry per table block): 50,000 entries × 16 bytes / 8,000 bytes = 100 blocks, which is why sparse indexes are much faster. (§5.2)

Scenario: A language school's Student table has a dense index on Email. One student changes only their Phone; another changes their Email. What happens to the index in each case?

Phone change: an update to a column that is not indexed does not affect the index. | Email change: like a delete followed by an insert. The entry for the old Email is deleted (marked as 'deleted'), and an entry for the new Email is inserted in sort order in the correct index block; if that block is full, it splits in two. (§5.2)