IT Lecture Notes by Mark Kelly, McKinnon Secondary College

Indexing

Just as binary trees can save huge amounts of time and effort searching through ordered data, indexes are the programmer's best friend when it comes to sorting large amounts of data. They are used especially in databases like Filemaker Pro and Access where search speed is crucial.

Instead of searching massive database files (which could be gigabytes in size), indexes are smaller files that are much more quickly searched and manipulated because they only contain a fraction of the original data. Take the following data

#	NAME	AGE	hundreds of other fields>>
1	John	66	etc
2	Bruce	34	etc
3	Tom	89
4	Mary	21
5	Fred	5
6	Gina	45
7	Xeno	12

To sort the records by name physically (actually moving Bruce's data to the start of the file and Fred to the second slot etc) would be both inefficient and ineffective. It would take ages to shift data around in memory or on disk, and it wouldn't work very well anyway. If Adam arrived, all the data would again have to be shifted so Adam could be inserted at the top. Also, if you decided to sort by age rather than by name, you'd have to move everything again.

Clearly, databases can't afford to be so wasteful. They have to work a bit smarter, and that's where indexes come in handy.

To sort the data above by name, an index is created containing only the data in the sort field...

#	NAME	AGE
1	John	66
2	Bruce	34
3	Tom	89
4	Mary	21
5	Fred	5
6	Gina	45
7	Xeno	12

Name index

2 - Bruce

5 - Fred

6 - Gina

4 - Mary

1 - John

3 - Tom

7 - Xeno

So the first record, when sorted by name, is record 2 (Bruce). Next is record 5 (Fred) etc. If Adam is added, his record is appended to the end of the file and only the index is re-created to add Adam to the sort order. This requires far less work than moving all of the other records down to slot Adam in at the top.

#	NAME	AGE
1	John	66
2	Bruce	34
3	Tom	89
4	Mary	21
5	Fred	5
6	Gina	45
7	Xeno	12
8	Adam	55

Name index

8 - Adam

2 - Bruce

5 - Fred

6 - Gina

4 - Mary

1 - John

3 - Tom

7 - Xeno

Key point: Data are stored in the order they arrive. Records are never physically shuffled about in memory or on disk.

The next benefit of indexes is that you can have as many of them as you like. To sort by age, you don't need to physically move records about: you just create a second index. Therefore you can instantly flip from sorting by one field to sorting by a different field.

#	NAME	AGE
1	John	66
2	Bruce	34
3	Tom	89
4	Mary	21
5	Fred	5
6	Gina	45
7	Xeno	12
8	Adam	55

Name index

8 - Xeno

2 - Bruce

5 - Fred

6 - Gina

4 - Mary

1 - John

3 - Tom

7 - Xeno

Age index
5 - 5
7 - 12
4 - 21
2 - 34
6 - 45
8 - 55
1 - 66
3 - 89

In short - indexes are good. They take a little work to create and maintain, but they hugely improve efficiency when handling lots of data.

Also see - Binary Trees

Back to the IT Lecture Notes index

Back to the last page you visited

Created 15 August 2007

Last changed: August 15, 2007 12:08 PM