Understanding the notion of an index

1. Consider the data in this file. Say you store the data as a list of tuples, as shown in this Python program. You can search the data, say by student id as you do in a query like SELECT name from student where ID = 45673. 
2. Since the data in the list is not ordered, the best you can do is a linear search. 
3. If you order the list by ID, you can implement a faster search, like binary search. 
4. What if you find yourself searching by name often? The ordered (by ID) nature of the data does not help. You are back to linear search. 
5. You can create an index on name, perhaps keeping all names in a binary tree, along with a link to the corresponding tuple in the list. That index can now be searched efficiently for a given name.