WEBVTT
Kind: captions
Language: en

1
00:00:00.149 --> 00:00:03.770
There are many different ways to put a shelf
of books in order.

2
00:00:03.770 --> 00:00:05.640
Alphabetically by author, or by title.

3
00:00:05.640 --> 00:00:08.380
By subject. Or by the colour of the spine.

4
00:00:08.380 --> 00:00:10.740
Those are all valid approaches
for different situations:

5
00:00:10.740 --> 00:00:13.849
if you’re a bookstore that has a lot of
customers coming in and saying

6
00:00:13.849 --> 00:00:17.560
“I don’t remember the title, but I know
it was red…”

7
00:00:17.560 --> 00:00:20.849
then sorting by colour is a reasonable approach.

8
00:00:20.849 --> 00:00:25.669
In 1876, an American librarian called
Melvil Dewey published a four-page pamphlet

9
00:00:25.669 --> 00:00:29.410
describing how he thought a public library
should be ordered.

10
00:00:29.410 --> 00:00:34.270
Before Dewey, books in many libraries were
ordered by when they were purchased.

11
00:00:34.270 --> 00:00:39.250
As new books arrived, they’d just be allotted
to a shelf or a box that matched their size,

12
00:00:39.250 --> 00:00:42.840
and there’d be a central card file somewhere
listing where everything was.

13
00:00:42.840 --> 00:00:45.850
You would have to ask a librarian if you wanted
a certain book,

14
00:00:45.850 --> 00:00:47.680
and they’d retrieve it for you.

15
00:00:47.680 --> 00:00:50.940
Just browsing the shelves wasn’t a thing.

16
00:00:50.940 --> 00:00:53.980
Dewey gave each subject an index number,

17
00:00:53.980 --> 00:00:57.650
and then said that the shelves should be ordered
by that number.

18
00:00:57.650 --> 00:01:01.930
Over the years, the Dewey Decimal system
became a standard.

19
00:01:01.930 --> 00:01:03.800
Dewey had solved a serious problem:

20
00:01:03.800 --> 00:01:08.140
how to sort and find information,
without having to bother the head librarian.

21
00:01:08.140 --> 00:01:10.330
And because books were
clustered by their subject,

22
00:01:10.330 --> 00:01:14.830
it encouraged general-interest
browsing of the shelves.

23
00:01:14.830 --> 00:01:16.720
Side note: while researching this,

24
00:01:16.720 --> 00:01:20.490
I found out that Dewey was a terrible person.

25
00:01:20.490 --> 00:01:22.920
Not in a “oh, but he was of his time”
way,

26
00:01:22.920 --> 00:01:27.870
like, he resigned from the American Library
Association because of sexual harassment complaints

27
00:01:27.870 --> 00:01:29.420
in 1905.

28
00:01:29.420 --> 00:01:32.470
How bad do you have to be in 1905 to get kicked-

29
00:01:32.470 --> 00:01:36.980
His sexist and racist biases made it into
the early versions of the Dewey Decimal system.

30
00:01:36.980 --> 00:01:40.440
Lots of libraries these days use completely
different classifications.

31
00:01:40.440 --> 00:01:43.670
But, yeah, we do still remember his name.

32
00:01:43.670 --> 00:01:48.520
Anyway, here’s the key point: by creating
a useful index and sorting by it,

33
00:01:48.520 --> 00:01:50.330
readers could find books more quickly.

34
00:01:50.330 --> 00:01:56.160
That same principle of indexing applies to
computers, and has since the early days.

35
00:01:59.100 --> 00:02:03.130
There are two basic ways that a
computer can search: linear and binary.

36
00:02:03.130 --> 00:02:05.190
Let’s say you’ve got a stack of cards.

37
00:02:05.190 --> 00:02:08.789
They’ve got numbers on them that are somewhere
between 1 and 50.

38
00:02:08.789 --> 00:02:10.729
and you want to find lucky number 13.

39
00:02:10.729 --> 00:02:12.760
If it’s a shuffled stack,

40
00:02:12.760 --> 00:02:15.159
then there’s no shortcut: you just run through,

41
00:02:15.159 --> 00:02:17.640
looking at one card after another
after another after another,

42
00:02:17.640 --> 00:02:20.150
until eventually you find number 13.

43
00:02:20.150 --> 00:02:21.769
That is linear search:

44
00:02:21.769 --> 00:02:24.779
going through every card in a stack,
every element in a list,

45
00:02:24.779 --> 00:02:27.230
until you find the one
or many that you’re looking for.

46
00:02:27.230 --> 00:02:29.430
That’ll work on any list, in any order.

47
00:02:29.430 --> 00:02:32.450
But most of the time, it will be slow.

48
00:02:32.450 --> 00:02:35.840
But what if the cards are in order by number?

49
00:02:35.840 --> 00:02:38.109
Sure, you have to spend some time to sort them.

50
00:02:38.109 --> 00:02:39.800
I’ve got a whole other video about that.

51
00:02:39.800 --> 00:02:41.400
But once you’ve done that,

52
00:02:41.400 --> 00:02:44.475
once they’re in order,
you can use a binary search.

53
00:02:44.475 --> 00:02:47.091
Binary not in terms of
zeros and ones on disk,

54
00:02:47.091 --> 00:02:49.406
but binary in terms of
splitting things in two.

55
00:02:49.406 --> 00:02:51.139
Look at the middle item of the list.

56
00:02:51.139 --> 00:02:53.840
Is it higher or lower than the number we’re
looking for, 13?

57
00:02:53.840 --> 00:02:55.760
So in this case, it’s lower.

58
00:02:55.760 --> 00:02:59.140
So we can forget about the first half of the
list, and we can do the same again.

59
00:02:59.140 --> 00:03:00.459
Look in the middle of what's left,

60
00:03:00.459 --> 00:03:02.670
forget about the side that we don’t want,
look in the middle,

61
00:03:02.670 --> 00:03:05.540
forget about the side we don't want,
and so on, and so on, and so on,

62
00:03:05.540 --> 00:03:08.069
until eventually we find the card we’re looking for

63
00:03:08.069 --> 00:03:10.590
or we know it’s not in the list at all.

64
00:03:10.590 --> 00:03:14.430
Okay, with eleven cards, binary search doesn’t
make much difference.

65
00:03:14.430 --> 00:03:16.019
But with a million cards,

66
00:03:16.019 --> 00:03:19.459
it is lightning-fast compared to linear search.

67
00:03:19.459 --> 00:03:22.200
Provided that the list is in order.

68
00:03:22.200 --> 00:03:24.019
But a stack of cards is a simple example.

69
00:03:24.019 --> 00:03:25.629
A database is much more complex.

70
00:03:25.629 --> 00:03:28.250
Let’s say we don’t just have numbers on
the cards:

71
00:03:28.250 --> 00:03:30.290
we also have letters,
and let's add some colours as well.

72
00:03:30.290 --> 00:03:35.749
We can’t sort the cards by more than one
of these properties at a time.

73
00:03:35.749 --> 00:03:36.889
So right now,

74
00:03:36.889 --> 00:03:41.150
I can use binary search for number, but not
for letter or colour.

75
00:03:41.150 --> 00:03:45.949
In the same way that librarians can sort their
books by title, or author, or colour,

76
00:03:45.949 --> 00:03:48.900
you can only optimise for
one property at a time.

77
00:03:48.900 --> 00:03:51.870
For everything else, you’ve got to run through
every book on the shelf,

78
00:03:51.870 --> 00:03:54.639
every card in the stack,
every item in the list.

79
00:03:54.639 --> 00:03:58.189
Unless you use indexes.

80
00:03:58.189 --> 00:04:01.439
Now, physically rearranging data on a hard disk,
moving the cards around,

81
00:04:01.439 --> 00:04:03.260
that’s called a “clustered index”.

82
00:04:03.260 --> 00:04:06.259
It’s like making sure your dictionary is
in alphabetical order

83
00:04:06.259 --> 00:04:08.040
because that's mostly how
you're going to use it.

84
00:04:08.040 --> 00:04:13.359
But a “non-clustered index” is like the
index at the back of a book, or a library catalogue.

85
00:04:13.359 --> 00:04:16.820
It’s a separate store of just the property
you’re interested in,

86
00:04:16.820 --> 00:04:18.620
stored in a simple, easy-to-access format.

87
00:04:18.620 --> 00:04:23.130
If I want to find the card with the letter
K on it?

88
00:04:23.130 --> 00:04:26.099
Well, I can do a binary search
through the index at speed,

89
00:04:26.099 --> 00:04:30.470
identify the number of the card, and then
use another binary search to go straight to it.

90
00:04:30.470 --> 00:04:32.440
If I want to pull all the green cards,

91
00:04:32.440 --> 00:04:36.360
I can pull just those out of the colour index,
index, note down all those numbers,

92
00:04:36.360 --> 00:04:38.940
and then pull just those cards.
There's no linear search happening anywhere.

93
00:04:38.940 --> 00:04:42.349
Again: it doesn’t make much difference with
eleven cards.

94
00:04:42.349 --> 00:04:44.940
But with a thousand, or a million, or a billion,

95
00:04:44.940 --> 00:04:49.229
that’s the difference between waiting hours
for a response to your query,

96
00:04:49.229 --> 00:04:51.560
and having it in a fraction of a second.

97
00:04:51.560 --> 00:04:56.870
Of course, each index that you add takes
time to create, and space to store.

98
00:04:56.870 --> 00:05:00.060
If your computer’s ever been slow because
of the “Indexing Service” on Windows,

99
00:05:00.060 --> 00:05:04.187
or “Spotlight Search” on Mac; that’s it
taking the time to

100
00:05:04.187 --> 00:05:07.840
run through all your files and index
all the properties that it can,

101
00:05:07.840 --> 00:05:09.870
so that when you type something
into your search bar,

102
00:05:09.870 --> 00:05:12.849
it’ll be able to reply as quickly
as possible.

103
00:05:12.849 --> 00:05:16.460
But every time you make any
change to your database,

104
00:05:16.460 --> 00:05:18.620
if you add, remove, or change something,

105
00:05:18.620 --> 00:05:22.060
you also have to keep the indices...
indexes... whichever, up to date.

106
00:05:22.060 --> 00:05:26.650
So there’s a skill in choosing which properties,
which fields in a database,

107
00:05:26.650 --> 00:05:28.860
you want to create indices for.

108
00:05:28.860 --> 00:05:31.150
If you’re only going to search by colour
once or twice a year,

109
00:05:31.150 --> 00:05:33.919
it might not be worth indexing.

110
00:05:33.919 --> 00:05:36.099
As with many things in computer science,

111
00:05:36.099 --> 00:05:40.069
there’s a trade-off between space and time.

112
00:05:40.069 --> 00:05:45.080
Now, Google say that their full search index
is 100 petabytes in size,

113
00:05:45.080 --> 00:05:49.419
and they’re customising every result from
it for every user, usually in under a second.

114
00:05:49.419 --> 00:05:51.539
Even after all the changes to Google over
the years,

115
00:05:51.539 --> 00:05:56.500
even after all the space that they’ve given
over to knowledge boxes -- and adverts --

116
00:05:56.500 --> 00:06:01.945
even after all the optimisation they’ve added
to give the user exactly what they want…

117
00:06:01.945 --> 00:06:08.297
Google still put the time it took to answer every query
on every desktop search result.

118
00:06:08.297 --> 00:06:10.009
Because they're still proud of it.

119
00:06:10.009 --> 00:06:13.939
Because the logistics and computer science skills
required to do that are the sort of thing

120
00:06:13.939 --> 00:06:16.250
that PhDs are written about.

121
00:06:16.250 --> 00:06:18.000
Or, because it’s a trade secret,

122
00:06:18.000 --> 00:06:20.750
they’re the sort of thing that commands
very, very high salaries.

123
00:06:20.750 --> 00:06:24.910
It’s a long, long way between Dewey
and his decimal system

124
00:06:24.910 --> 00:06:26.611
and the Google search result.

125
00:06:26.611 --> 00:06:31.682
But the basic principle, "create an index",
is the same.