SCC.121: Indexed Retrieval

Flashcards about Indexed Retrieval

What is Indexed Retrieval?

For storing and retrieving objects or records, often based on alphabetic keys.

What are the time complexities of Linear and Binary Search in the context of searching arrays?

Linear Search - O(N): linear time, Binary Search - O(log2N): logarithmic

What is the role of a 'key' in indexed retrieval?

An attribute of each object used as a unique identifier for storage and retrieval, allowing objects to be stored in sorted order for binary search.

What is the purpose of an index array in indexed retrieval?

An array constructed to index the first element of each section of sorted keys (e.g., first 'A' record, first 'B' record, etc.).

How does Indexed retrieval with a linear search work?

Take the first letter L from name; convert L to numeric value V; P = Index[V]; if (P<0) then no records start with letter L. Iterate to find the correct record or determine it's not present.

What is the efficiency of indexed retrieval with linear search?

Worst case is O(N), but in practice, it can be significantly faster than linear search without indexing, depending on the distribution of keys.

What is the efficiency of indexed retrieval with binary search?

Worst case is O(log2N), but in practice, could be much faster than binary search without indexing, depending on the size and distribution of sections.

What are Collisions in the context of indexed retrieval?

A situation where multiple keys map to the same index in a storage structure.

What is Collision-free storage?

An approach where the set of words is held in an array, and the index of each word is determined by its first letter, allowing quick checks for word existence.

Briefly explain the Collision-free storage algorithm

Take first letter L from name; convert L to numeric value V; if (STORE[V].key == name) return STORE[V];

What is the time complexity of collision-free storage?

Constant time, O(1).

How can indexed retrieval be used as a solution for dealing with collisions?

Keys are put into a sorted array, and an index array is used to find the relevant section, but the index array must be recomputed when inserting extra data.

What is a solution using chains (linked lists) for collisions?

Using chains is a dynamic solution where each element of an array points to a chain (linked list) of objects whose keys share the same starting letter.

Briefly explain the indexed retrieval algorithm using chains, using names as an example (LUcas as name and V as numeric value and P as chain pointer

Take first letter L from name; convert L to numeric value V; obtain chain pointer P from STORE[V]; iterate through chain to find matching key.

What is the efficiency of dealing with collisions using chains, and what are its advantages?

Worst case: O(N), Practically: Much faster if objects are distributed across many chains, with the advantage of easier insertion and no need to recompute the index.