06 Indexing

Question 1

files organisation

Answer 1

• 1 database contains 1 or more tables
• 1 table contains 1 or more tuples
• 1 file contains 1 or more data pages
• given query, DBMS figures how to enable efficient access to desired data pages

Question 2

3 methods of organisation

Answer 2

1. heap files
   - random order
   - scan all records
2. sorted files
   - good for order sensitive data retrieval and range search
3. indexes
   - additional data structure to optimise retrievals
   - speed up search
   - fast update

Question 3

what is indexing

Answer 3

• goal: fast
• data structure to organise and optimise files
• use specific search keys for each tuple
• data entry recorded in index file

Question 4

types of index data structure

Answer 4

1. hashing
   - collection of buckets containing data entries
   - buckets have size limits
   - each bucket contains key, eg. key: lastname = “smith”
   - equality search
2. tree
   - equality and range search
   - hierarchy structure
   - B+ tree most popular

Question 5

B+ tree

Answer 5

• all data is in the leaf node
• leaves are all on the same level (balanced)
• leaves are all linked
• min 50% occupancy