Topics to Learn

• Index
• Dense index vs sparse index
• Primary index vc secondary index
• Multi-level index
• Indexed Sequential Access Method (ISAM)

Basic Problem

• If the sids are sorted, we can use binary search
• But looking up at the names might be very slow

Index: Basic Idea

• Build an "index" on the table

  • An auxiliary structure to help us quickly locate a tuple given a "search key"

    

  • The index contains matainformatino of our table

Dense, Primary Index

• Primary index (=clustering index)
  • Underlying table is sequenced by a key
  • Index is built on on the same key (=search key)
• Dense index
  • One (key, pointer) index entry per every tuple

Why Dense Index?

• Ex:

  • 100,000,000 tuples (900-bytes/tuple)
  • 4-byte search key, 4-byte pointer
  • 4096-byte block. Unspanned tuples

• Q: How many blocks do we need form the table (how big)?

     floor(4096/900) = 4 tuples per block
  
    so we need 100000000/4 = 25000000 blocks ⇒ 100GB
  

• How many blocks do we need if we index it?

  4096/8 = 512 tuples per block, 100000000/512 = 19513 blocks ⇒ 800MB

Sparse, Primary Index