Indexing And Hashing

Front 1

Hash Table

Back 1

- A data structure used to implement an associative array, a structure that can map keys to values

- Uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found

- O(1)

Front 2

Hash Function

Back 2

- Function which, when applied to the key, produces an integer which can be used as an address in a hash table (index into an array of buckets)

Front 3

Hash Index

Back 3

- Organizes the search keys with their associated pointers into a hash file

- Consists of a collection of buckets organized in an array

- Through linked lists, multiple items can be associated with one index because of this Hash indices are often called buckets

Front 4

Operations for Creating a Hash Table

Back 4

1. Creating an array: The actual table where the data is stored

2. Creating the Hash Function

Front 5

Uniform Hash

Back 5

When the indices produced by the hash function (into an array) are equally likely to be generated

Front 6

Problems with Hash Function

Back 6

- Ideally, the hash function will assign each key to a unique bucket (index), but this ideal situation is rarely achievable in practice

- Most hash table designs assume that hash collisions—different keys that are assigned by the hash function to the same bucket—will occur

Front 7

Complexity of Hashing

Back 7

- In many situations, hash tables turn out to be more efficientthan search trees or any other table lookup structure

- For this reason, they are widely used in many kinds ofcomputer software, particularly for associative arrays,database indexing, caches, and sets

Front 8

Procedure for Hash Index

Back 8

- Puts a pointer to a record in the bucket based on the hash of that particular record’s key

- A hash function “h” maps a search-key value to an address of a bucket

- Commonly used hash function: hash value mod n_B where n_B is the number of buckets

Front 9

Procedure for Hash Function

Back 9

1. Creating the original hash code for the hash key

2. Transferring this number to a smaller number to be used as index for the key

Front 10

Other Applications of Hash Functions

Back 10

- Used to build caches for large data sets stored in slow media such as a slow Hard Drive. Frequently accessed data is saved in cache and can be accessed in a very short time

- Computer operating systems use hash functions for fast access of key words and commands

Front 11

Good Hash Function

Back 11

- Create hash codes that permits the widest distribution of keys to various index values of the hash table.

- It should uniformly distribute the keys

Front 12

Perfect Hash Function

Back 12

- Create such a unique code for each key in the data that the probability of two keys having the same code is zero.

- Such a hash function is ideal but rarely does it exist

Front 13

Collision

Back 13

- When 2 keys hash to the same location in the hash table

- Note: a good hash function distributes the elements uniformly over the hash table, this keeps the number of collisions within manageable limits

Front 14

Chaining

Back 14

- Collision Resolution Method

- When there is a collision (key hashed to an occupied slot), the new key is stored in an overflow list.

- Each incoming duplicate entry is linked at the end of this list chained to the index

- Solution: make the size of the hash table (m) larger than the number of key value pairs (33%)

Front 15

Linear Probing

Back 15

- Collision Resolution Method

- Will look onto the subsequent hash elements until the first free space is found

- The size of the hash table (m) must be bigger than the number of elements so that some empty slots areavailable

Front 16

Hashing with Databases

Back 16

- Oracle does not have hash indices built in

- MySQL does

Front 17

Indexing

Back 17

- Something to facilitate search

- Used in Databases

- Purpose: improve the speed of data retrieval

Front 18

Two Main types of Indexing

Back 18

- Ordered Index

- Hash Index

Front 19

Ordered Index: Primary Index

Back 19

- If the file containing the records is sequentially ordered, the index whose search key specifies the sequential order of the file

Front 20

Ordered Index: Secondary Index

Back 20

- Indices whose search key specifies an order different from the sequential order of the file

- Improve the performance of queries on nonprimary keys

- Impose serious overhead on database modification: whenever a file is updated, every index must be updated

Front 21

Dense Index

Back 21

- An index record appears for every search key value in file

- This record contains search key value and a pointer to the actual record

Front 22

Sparse Index

Back 22

- Created only for some of the records

- To locate a record, we find the index record with the largest search key value less than or equal to the search key value we are looking for

- We start at that record pointed to by the index record, and proceed along the pointers in the file (that is, sequentially) until11 we find the desired record

Front 23

Dense Indicies

Back 23

- Don’t give us much of a bonus on an ordered table –a primary index that is dense on an ordered table is redundant!

- A primary index on an ordered table is always sparse

- Otherwise (unordered) use dense or secondary indices

- Dense indices are faster in general

Front 24

How much indexing to do?

Back 24

- Read-heavy DBs – can index a lot (if got the memory to do it)

- Write-heavy DBs – index sparingly! (take a balanced approach)

- Write-ONLY DBs – one or no index (e.g. log table)

Front 25

Two-Level Sparse Index

Back 25

- If index is too large to be kept in main memory, one search results in several disk reads

- If there are no overflow blocks in the index, we can use binary search

- If index has overflow blocks, then sequential search typically used

- Solution: Construct a sparse index on the index