Quiz

Can you explain why we might have KEY `nm` (nm) and FOREIGN KEY (`nm`) in further detail?
Sure. That situation occurs with the credit table, where nm is a FOREIGN KEY into the person table.
The nm is *not* unique in the credit table, though it is in the person table.
We build indexex on nm and tt so that lookups by either of those values will be fast, and we will use those indexes for common, normal queries like:
```
    select * from person
    inner join credit using(nm)
    inner join movie using (tt)
    where Title = 'Barbie';
```
Now, the confusing part is that MySQL calls the index a KEY, and describes it as such if you do "show create table", as we saw in the reading. That's an misleading bit of terminology that we will have to live with. It's NOT a KEY in the way that we have been using that term.
Here's what MySQL does:
```
PRIMARY KEY (tt, nm)   -- unique, identifies a row
UNIQUE KEY (x)         -- column "x" is unique in this table
KEY (tt)               -- ordinary, non-unique index
INDEX (tt)             -- exactly the same as KEY here        
```
How can we decide when it's better to use indexes to make queries faster or if it's better to not use them for a faster insert/delete?

This is an excellent question without an easy answer. It has to do with the workload of the table.
A table for, say, credit card transactions, will have to deal with lots and lots of inserts, all the time. So, keeping inserts fast is important. How often do we look up a credit card transaction? Monthly, when we send out statements? So, queries might be relatively rare.
In a situation like that, we might eschew indexes.
OTOH, a table for movies will do lots of queries, all the time, but rarely insert/update/delete a movie. So, spending additional effort in an insert/update/delete to maintain indexes (on title, director, and what not) will pay off.
Could you explain B- and B+ trees again? I'm having a hard time finding the connection of those with the rest of the reading, or how to even implement a B-tree in the context of SQL

YOU won't implement a B-tree. MySQL does, maintaining it inside the INNODB representation of a table.
If you want, you can visualize a B-tree as a sorted array, because the leaves of a B-tree are a sorted array.
The internal nodes of a B-tree make sure that read/inserts/deletes are all O(log n) time.
I'll draw a picture.
Could you explain a bit more of how B-trees work? I don't understand how increasing the base of the logarithm changes the complexity of accessing a record to O(1).
Increasing the base doesn't literally bring the complexity to O(1); that was a bit of an exaggeration.
But not by much.
Suppose that the branching factor is 100. That is, we can fit 100 keys into each block.
- A tree of depth 1, can handle 100 keys, all accessed in 1 step
- A tree of depth 2, can handle 10,000 keys, all accessed in 2 steps
- A tree of depth 3, can handle 1,000,000 keys, all accessed in 3 steps
- A tree of depth 4, can handle 100,000,000 keys, all accessed in 4 steps
- A tree of depth 5, can handle 10,000,000,000 keys, all accessed in 5 steps
- A tree of depth 6, can handle 1,000,000,000,000 keys, all accessed in 6 steps
Since O(1) means bounded by a constant, if we choose a constant like, 7, we can kinda say that this is O(1), because in terms of practical, real-world amounts of data, we'll never exceed 7.
And if we increase the branching factor to 200, the tree gets even shorter and bigger.