Chapter 17: Indexing Structures

These flashcards cover key concepts related to indexing structures in database systems as presented in the lecture notes.

Index

An auxiliary file that makes searching for records in a data file more efficient.

Primary Index

An index defined on an ordered data file, where the file is ordered based on a key field.

Clustering Index

An index defined on an ordered data file with non-key fields, pointing to the first data block with distinct field values.

Secondary Index

An index that provides a secondary means of accessing a file, allowing duplicate values.

Dense Index

An index that contains an entry for every search key value in the data file.

Sparse Index

An index that has entries for only some search key values, usually for the first record in each block.

Access Path

The method by which an index enables access to data records.

Block Anchor

The first record in a block referenced by a primary index.

Multilevel Index

An index that consists of multiple levels of indexes, leading to an ordered file.

B-Tree

A type of search tree that maintains sorted data and allows for efficient insertion and deletion.

B+-Tree

A variation of B-Tree where all data pointers exist only at the leaf level.

Insertion Problem

The challenge of inserting new index entries into a B-Tree or B+-Tree without violating structure.

Deletion Problem

The challenge of deleting an entry from a B-Tree or B+-Tree while maintaining order.

Binary Search

A search algorithm used on index files to efficiently find pointers to file records.

Record Pointer

A pointer that directs to an individual record in the data file.

Disk Block

A unit of storage on disk that holds a fixed number of records.

Search Key Value

The value on which the database items are indexed.

Overflow Block

An additional block used when a data block is full and more records need to be added.

Dynamic Size Issue

A challenge faced when clusters of records expand beyond their allocated space.

Key Field

The specific field in a record that is used for ordering or indexing.

First-level Index

The initial index created, usually pointing to the data file.

Second-level Index

An index that points to the first-level index.

Key Sequential Reads

The ability to read records in the order of their keys.

Search Tree

A data structure that enables search operations through nodes and pointers.

Record

An individual entry in a data file, containing data values.

Ordered Data File

A data file that is arranged in a specific order based on key fields.

Non-key Field

Fields in a record that do not serve as the primary key but may still be indexed.

Key Value

The value assigned to a key field in a record.

Insertion Sequence

The order in which records are inserted into a B+-Tree.

Data File

The main file that contains actual records in the database.

Reorganization

The process of restructuring an index or data file to enhance performance.

Node

An element of a search tree, containing keys and pointers.

Underflow

A condition that occurs when a node has fewer keys than allowed after deletion.

Merge Operation

A process where two nodes are combined into one to maintain tree balance.

Pointer

A reference to records or nodes within an index or data structure.

Unique Value

A value that appears only once within a specific field across all records.

Duplicate Value

A value that appears multiple times within a specific field across records.

Input Operation

Inserting data or index entries into a structure.

Output Operation

Retrieving data or index entries from a structure.

Record Compression

A method to reduce the size of records in a data file.

Dynamic Indexing

The capability of an index structure to adjust size based on data volume.

Static Indexing

An index that does not change in size regardless of data adjustments.

Efficiency

The effectiveness and speed of operations performed on an index.

Database System

A software system to manage databases, including storage, retrieval, and update operations.

Insertion into B+-Tree

The process of adding a new value and restructuring tree nodes if necessary.

Deletion from B+-Tree

The process of removing a value, which may require tree adjustments.

Search Operation

The process of finding records in a data file using an index.

Multi-level Structure

An index setup with more than one level for optimal access paths.

Primary Key

A unique identifier for a record in a database table.

Candidate Key

A field that can potentially serve as a primary key.

Data Retrieval

The process of accessing and obtaining data from a database.

Index File

A file that contains index entries pointing to the locations of data records.

Field Value

The actual data stored in a specific field for a record.

Overflow Handling

Strategies implemented to manage excessive data beyond current storage.

Record Structure

The arrangement and organization of data fields within a single record.

Block Pointer

A reference to a specific disk block in a data file.

Lossy Structure

An indexing or organization method that may lose some efficiency or detail.

File Organization

The method in which records are stored and accessed within a data file.

Logical Structure

The abstract representation of data organization in a database.

Physical Structure

The actual storage format of data on disk.

Data Indexing Techniques

Methods used to create and manage indexes for efficient data access.

Key Distribution

The arrangement of key values in the index, affecting performance.

Positioning Strategy

The method by which records are stored and retrieved based on their order.

Retrieval Path

The sequence of operations followed to access a desired data record.

Buffer Management

The skill of managing temporary data storage for better index performance.

Data Integrity

Ensuring the accuracy and consistency of data within the database.

Concurrency Control

Methods to manage simultaneous operations in a database system.

Scalability

The ability of a system to handle growth and increased demand.

Metadata

Data that provides information about other data, facilitating indexing and retrieval.

Normalization

The process of organizing data to minimize redundancy.

Data Normalization Techniques

Strategies used to optimize database structure and indexing.

Key Clustering

The organization of records by grouping similar keys together.

Dynamic Record Organization

The adjustment of record placement based on changing data.