Instructor: Hi guys and welcome back.
In this video we're going to learn what a SQL index is.
This is going to be a slightly more theoretical
lecture than the ones before, so please
do bear with me, but it's important to understand
SQL indices, at least on the surface.
Or is it indexes? I don't even know.
So, here's the gist of it. An index is associated
with a specific column in a table,
and it helps speed up filtering and sorting operations,
really anything that uses that column specifically.
But it slows down writing to the table.
So, clearly, the index is going to help you out,
it's going to be useful if you are reading
a lot of data from a table, filtering and sorting,
and you're no writing that much.
Here's how they work. Let's say we've got this table here.
This is a pretty long table. We've got 12 people in it.
They have their names, years experience, and salary.
Let's say that the ID column is the primary key,
and most database systems are going to create
an index for primary keys for you.
So here is our index on the right.
Notice that we've picked somewhere amongst the middle
of our table to be the top of our index tree.
And then the database system is going to build out
this tree by putting less than eight on the left of it
and values greater than eight on the right.
So three and five go to the left of eight,
11 has gone to the right,
and then, similarly, for those nodes
like, for example, three and five, we've got
values less than three on the left,
values between three and five in the middle,
values greater than five on the right.
And so the database system is going to do
all of that for us. It's going to construct this tree
parting from the index.
And here we can assume that the ID column
is a primary key. Most database systems are going to
make indices out of primary keys for you.
So here's how they work.
Imagine we're looking for an employee with ID 9.
Normally, without an index, we just start at the top
and go through the rows one by one, searching.
So, we would have something like this,
we would start at the first row,
then we would move over to the second row,
it's not that one, so we move over to the third row,
and it's not that one, and so you get the gist of it.
It goes on and on until you get to the 9th row
and that's the one that matches.
Clearly, not so fast. You have to go through
at least nine numbers, in this case,
to find the one you want.
With an index, it's going to be a little bit different.
You need fewer jumps. You need exactly
log of N jumps, in fact.
The mathematics for that are not going to be explained
in this video, but you need three jumps
because you start at eight, then you go to 11,
and then you go to nine, and you find it there.
Something important about these indices,
well, it's a feature of B-trees, which is what an index is,
is that no branch must be much longer than the others.
So that's an interesting problem
when you start to add new numbers.
Clearly, for example, if we wanted to add the number,
let's say, 6.5 for the purposes of example,
and then you would add it somewhere around here,
but then that makes this branch longer than the others,
so when you start adding new numbers,
sometimes the binary tree has to move things around
to make sure that the branches
are not too different in length.
So how do we code a B-tree? That's what this is.
We don't have to. You don't need to,
we're not going to teach you how to code a B-tree.
The database does it all for you when you create an index,
it's just interesting to know what it's structured like
so that you know why it's faster.
But it's important to understand that
an index does affect performance.
Faster reads when filtering or sorting,
basically anything that uses the column
specifically for an operation is going to be faster
because the database is going to be able
to use that tree to find things,
rather than going through the table itself,
but it's going to be slower
because every time we want to insert a row,
the index need to be kept updated
and branches potentially moved around
so that they are the same length,
or close to the same length.
Note that an index is a table, so you also need
more disc space to store the index if you create one.
All right, let's go and add an index
to our app's database.
Note that normally you'll only add indices
when queries are taking very long.
If your queries are taking long, that's a sign
that you can use an index to speed things up,
if the slowdown is happening in a WHERE clause
or an ORDER BY, or something like that.
Don't add indexes everywhere, or indices everywhere,
because that's going to be a waste of processing power
and disc space.
All right, let's go and do that.