Database Indexing and File Organization Analysis
Uploaded by
Faizan Bashir SidhuDatabase Indexing and File Organization Analysis
Uploaded by
Faizan Bashir SidhuCommon questions
Powered by AICreating indexes reduces the query execution time by enabling quicker data retrievals at the expense of increased storage and maintenance overheads on DML operations like insert, update, or delete. The process should be approached systematically, starting by assessing query execution times without indexes, then adding indexes one at a time, using tools like PostgreSQL's EXPLAIN to identify performance changes. Recording results of each step ensures that benefits outweigh overhead costs, helping highlight the most impactful indexes in terms of query performance enhancement .
ISAM (Indexed Sequential Access Method) indexes maintain static structure, meaning after initial setup, it doesn’t adjust automatically which can cause imbalance over time. B+ Trees, on the other hand, dynamically adjust as data is inserted and deleted, maintaining balance at all times. B+ Trees are generally preferred for databases requiring frequent updates or where the data set size varies over time, as they handle insertions and deletions more efficiently without imbalance. ISAM may be preferred in systems where the data set is static and where read access far exceeds write access .
A tree index, like a B+ Tree, is efficient for range queries due to its ordered nature but tends to be slower for exact match queries compared to hash indexes. Hash indexes, using mechanisms like Linear Hashing, allow fast exact match queries because they offer a constant average search time, typically involving fewer disk I/Os due to direct entry location without needing to traverse tree levels. When databases handle frequent exact match lookups versus range queries, a hash index will significantly improve performance .
Analyzing data distribution informs which columns are most selective and can, therefore, significantly benefit from indexing. For example, queries searching for specific departments by location and budget require indexes on those columns if values are not uniformly distributed, such as location being much less frequent or budget having a large range. Such analysis ensures that high-cardinality columns are indexed, leading to more efficient query plans where fewer rows are scanned, thus speeding up retrieval times significantly .
The three main alternatives for sorting information in a data entry of an index are sorted files, heap files with an unclustered tree index on the search key, and heap files with an unclustered hash index. In a clustered index, the data entries are stored in the order of the index key, making it suitable for range queries. In contrast, an unclustered index maintains a separate structure from data file, so data entries are stored in different orders than index keys. Sorted files are naturally clustered by the sorting key, making them efficient for range queries but costly for insertions and deletions. Whether an index is clustered or unclustered depends on how data entries are arranged in relation to the data file structure .
Inserting entries into a B+ tree in sorted order leads to frequent node splits since each new entry is placed into an already full leaf node. This often results in under-utilized trees with many half-empty nodes. For example, if a B+ tree has nodes that can each hold four entries and entries 'A' to 'G' are inserted in sorted order, every fifth entry requires a split. This continuous splitting results in a tree with many nodes having only two entries, defying the purpose of packing nodes as densely as possible for performance .
Bulk-loading a B+ tree is preferable because it allows the structure to be built in a single operation optimized for space and search efficiency, minimizing node splits or merges that occur during individual insertions. When data is already sorted, bulk-loading can create a balanced B+ tree with high storage utilization and reduced I/O operations compared to record-by-record insertion, which can result in a non-optimized tree where less data fits per node, increasing search and storage costs .
The worst-case cost for an equality search in a Linear Hashing index where each page holds 10 records with 80% average storage utilization is determined by how overflow pages are managed. If overflow buckets need to be checked, the search could involve accessing multiple pages, upping the disk I/O. This scenario occurs when a bucket has overflowed and all its overflow pages need to be examined to ensure the queried record isn't amongst them. Therefore, worst-case occurs when buckets have an optimal split maintained, minimizing overflow chain length, but still requiring multiple page accesses .
Extendible hashing uses a directory of buckets, where each bucket can hold multiple entries. The principal idea is to use a directory of pointers to buckets to handle dynamic partitioning of data entries. The global depth indicates the number of bits used to index into the directory, while the local depth indicates bits used within the bucket. This scheme allows for dynamic growth without needing to reorganize the entire data structure, as only specific buckets that overflow are split, preserving efficiency in insertions and searching .
When dealing with variable-length records, a directory of pages is often more efficient to manage space allocation because it can better adapt to changing record sizes without the need to physically rearrange records within each page. The directory structure keeps track of which pages have available space for new or expanding entries, optimizing both space utilization and the time required to locate records. In contrast, list-based organizations tend to become inefficient as they struggle with fragmentation and space reclamation .