🎓 A1Learner
🔍
0 of 47 lessons completed

Database Indexes

A database index is a lookup structure that finds a row from a key without reading every row. The index trades a little extra storage for far fewer steps on each lookup.

Finding a row by scanning

This scan searches 1,000 generated rows one by one. The count shows how many rows it checked before the match.

rows = list(range(1, 1001))
target = 1000
checks = 0
for row in rows:
    checks = checks + 1
    if row == target:
        break
print("Comparisons:", checks)
print("Found row:", row)

Finding a row through an index

An index maps each key straight to its row. The lookup counts as a single step however large the table grows.

rows = list(range(1, 1001))
index = {}
for row in rows:
    index[row] = row
target = 1000
lookups = 1
found = index[target]
print("Lookups:", lookups)
print("Found row:", found)

Early rows and late rows

A scan checks few rows for an early target and many rows for a late target. The index count stays the same for every target.

rows = list(range(1, 1001))
index = {}
for row in rows:
    index[row] = row
for target in [10, 500, 1000]:
    checks = 0
    for row in rows:
        checks = checks + 1
        if row == target:
            break
    print("Target", target, "- scan checks:", checks, "- index lookups: 1")

Example

orders = list(range(1, 1001))
index = {}
for order in orders:
    index[order] = order
target = 874
checks = 0
for order in orders:
    checks = checks + 1
    if order == target:
        break
print("Scanning for order 874:", checks, "comparisons")
print("Index lookup for order 874: 1 lookup")
print("Found order:", index[target])

Key points

  • Scan: a lookup without an index checks rows one by one until it finds a match.
  • Index: a lookup with an index goes straight from the key to the row that carries it.
  • Use an index to make a lookup fast when the same field is searched again and again.
  • Index cost: the database updates the index each time a row is added or changed.

In this example, a scan and an index both search the same orders for the same order. The scan count grows with the position of the order, and the index lookup stays at a single step.

Note

An index helps lookups on its own key, and it does not help lookups on other fields.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

A lookup checks every row one by one, and it grows slower as the table grows. What removes most of those checks?