Indexed Retrieval

Introduction to Index Retrieval

  • Key Concept: The notion of keys is crucial for index retrieval.

    • Requires an identifier to store and retrieve corresponding data.

Structure of an Index

  • Index Explanation:

    • Each letter corresponds to an index number for data storage and retrieval.

    • Index Zero: Points to the first element of the storage (a begins).

    • Example:

      • Index 0 points to the start of entries for the letter 'A'.

      • Index 1 points to the entry for 'B'.

  • Array Structure:

    • For the letter 'B', the fourth location in the array corresponds to Index 1 (i.e., the entry starts at location 4).

  • Example of Searching:

    • Searching for "Christoph":

    • Searching sequentially through Caden, Charlotte, and Chris but not Christoph.

    • If searching hits a letter that is greater, the search can be terminated early (if we reach an entry that starts with 'D', Christoph cannot be there).

Search Complexity

  • Worst Case Complexity:

    • Complexity of searching through the index can vary.

    • If searching requires traversing many entries, it could be up to the size of the store.

Collision Handling

  • Definition of Collision:

    • A collision occurs when two entries want to occupy the same index position.

    • Example:

    • The entries "Chris" and "Christos" can create a collision.

  • Handling Collision:

    • Shift Method:

    • If a collision occurs (for example, with 'K' before 'Christos'), earlier entries must be shifted down to make space.

    • Shifting creates free space for the new entry, such as "Christophe" at a new index (example: from index 10 to index 11).

  • Updating Index:

    • After shifting, the index must be updated to reflect the new positions of entries (i.e., starting point for letter 'D' might need updating due to shifts).

Complexity of Collision Handling

  • Worst-case Complexity of Shifting:

    • The complexity of shifting entries during collision handling is proportional to the total size of the store (i.e., you might need to shift everything).

    • The established index can be adjusted in constant time due to the small fixed number of entries (26 letters in the alphabet).

Alternative Methods for Handling Collisions

  • Using Linked Lists:

    • Instead of an array, a linked list can be utilized to handle collisions.

    • Structure:

      • The indexed array points to linked lists with different entries for each letter.

    • Benefits of Linked Lists:

    • While efficiency gains may be minimal, practical advantages can arise from using lists to manage collisions more flexibly.

Conclusion and Future Topics

  • Summary of Today's Lecture:

    • Focused on index structures, search complexities, collision handling strategies, and alternative methods (linked lists).

    • In the next lecture, the concept of ad hoc indexing will be explored further.