Shared Flashcard Set


COMP3017 - Lecture 3 (A) - Access Structures
COMP3017 - Lecture 3 (A) - Access Structures
Computer Science
Undergraduate 3

Additional Computer Science Flashcards




What are characteristics of sequential files?
  • Tuples of a relation are sorted by their primary key
  • Tuplues are then distributed among blocks in that order
  • Common to leave free space in each block to allow for later insertions
What are the tradeoffs to maintaining an index?
  • Maintaining one costs processor time
    • When entries are added, index must be updated
    • Index must be maintained to make good use of resources
  • There is a tradeoff between
    • Rapida access when retreiving data
    • Speed of updating the database
What is a dense index?
  • Sequence of blocks holding only keys and pointers to records
  • Entity for every record in data file
  • Blocks of index are in same order as those in the data file
  • Key-pointer pair much smaller than record
  • Advantages
    • Fewer blocks than data file, fewer disk accesses
    • Keys are sorted, so we can use binary search
    • Can keep in main memory if small neough (no disk accesses)
What is a sparse index?
  • One key-pointer pair per block of data file
  • Can only be used if data file is sorted by search key
  • Uses less space than dense index
  • Takes longer to find key than dense index
What is a multi-level index?
  • Index file may cover many blocks
  • May still need many disk acceses
  • Use spare index over the first index
  • Can't be a dense index (would use the same nuber of blocks as the index being indexed)
  • Can create a third level index, but in general prefer B-trees
What are some notes on pointers?
  • Block pointers (as used in sparse indexes) can be smaller than record pointers (used in dense indexes)
    • Physical record pointers consist of a block pointer and an offset
  • If file is contiguous, then we can omit pointers
    • Compute offset from block size and key position
What is the tradeoff of sparse vs dense indexing?
  • Sparse
    • Less index space per recor can keep more of index memory
    • Better for insertions
  • Dense:
    • Can tell if a record exists without accessing file
    • Needed for secondary indexes
Show an example of an insertion in a Sparse index where there's no space between the blocks, where it should be inserted
What are some characteristics of secondary indexes?
  • Unlike a primary index, does not determine placement of records in data file
  • Location (order) of records may have been decided by a primary index or another field
  • Secondary indexes are always dense
  • Pointers are record pointers not block pointers
  • May have higher levels of sparse indexes above the dense index
Show the ways Dense index can approach duplicate keys



How can sparse indexes deal with duplicate keys?
These would just point to the first instance of each value
How can secondary indexes deal with duplicate keys?

There can be several solutions:

  1. Repeated entries
    • Problems:
      • excess disk space
      • Search time is an overhead
  2. Drop repeated keys
    • Problem with variable size records in index
  3. Chain records with same key (linked list)
    • Problems:¬†
      • Need to ad fields to records, and need to follow a chain
  4. Indirection via buckets of pointers
    • Advantages:
      • If we have multiple secondary indexes on a relation, we can calculate conjunctions by taking intersections of buckets
      • Don't need to examine data file
What are the advantages and disadvantages of conventional indexes?
  • Advantages:
    • Simple
    • Index is sequential file and good for scans
  • Disadvantages:
    • Inserts expensive¬†
    • May lose sequentiality & balance
Supporting users have an ad free experience!