According to Wikipedia
A database index is a data structure that improves the speed of data retrieval operations on a database table at the cost of slower writes and increased storage space. Indexes can be created using one or more columns of a database table, providing the basis for both rapid random look ups and efficient access of ordered records. The disk space required to store the index is typically less than that required by the table (since indexes usually contain only the key-fields according to which the table is to be arranged, and exclude all the other details in the table), yielding the possibility to store indexes in memory for a table whose data is too large to store in memory.
In a relational database, an index is a copy of one part of a table. Some databases extend the power of indexing by allowing indexes to be created on functions or expressions. For example, an index could be created on upper(last_name), which would only store the upper case versions of the last_name field in the index. Another option sometimes supported is the use of "filtered" indexes, where index entries are created only for those records that satisfy some conditional expression. A further aspect of flexibility is to permit indexing on user-defined functions, as well as expressions formed from an assortment of built-in functions.
When I worked on running dive meets (springboard and platform diving) for my daughter, we had a system where people would turn in dive sheets based on age brackets, gender, and diving level. At first, we had just one inbox for the divers to turn in their dive sheets. With a total of 50 divers we could answer the questions of how many girls vs. boys are there, how many 10-11 years olds, how many novice or junior Olympic levels are there. We had to cycle through the whole pile to get those questions answered each time, but we could answer the questions pretty quickly. As the season progressed, we started having more divers come, and when it go up to 500 divers, having the one in box was crazy and it took a lot of time to answer those questions.
In the same way, using a database, a small number of records within a table can be managed pretty efficiently without any indexing. When a question is asked of the database (filtering), the database system cycle throughs ALL of the records noting which records should be included based on the filtering criteria (ie: State='CA'). The time it takes to do this is unnoticeable until about 10 thousand records or so. Now you start noticing a lag time, but, it is still acceptable and you are too busy to deal with it. Time moves on, the number of records in your table is increasing (which is good!) and now your waiting 10-15-20 seconds. Then someone imports 50,000 records into the table and boom, you start getting timeouts. You say, "this worked this morning! And I did not change anything." You have just crossed over into the "Indexing Zone."
These types of issues sneak up on you unless you have a completely static list of people to send email too. It will happen! Now even the most seasoned database programmer can get caught in this trap. The only way to really make sure things are in tip-top shape is awareness and maintenance.
Indexing is kind of like presorting. Say you have a table with basic contact information in it (name, city, state, etc.). When you add a record to the table without having any indexing, all you are doing is simply appending a piece of data onto the end of the table, no order, no nothing. Contact your database administrator today to start indexing your data and improve your email marketing performance.