How indexing works in magento

There are different kind of indexes in Magento.
All of the indexers are there to make things run faster.
I will cover here only a few of them.

Flat Index
There are 2 such indexes. One for categories and one for products.
By default the category and product entities (and customers and customer addresses but they are not important in this situation) are EAV entities. This is very nice for extensibility. But it's a performance killer because in order to get all values for all the attributes you need a lot of joins or multiple queries.
Here is where the flat indexer comes into play.
It transforms the EAV structure into a flat structure. I mean it creates a table (one for each store view in Magento) that has one column corresponding to an attribute. This makes selects faster. For categories all attributes are converted to table columns. For products only the ones you mark as 'Used in product listing' because you can sell all types of products with different attributes and creating one table with a gazillion columns may not be possible.
Also, some products may be disabled or may not belong to a certain website and there is no need to include them in the entries to search. They are excluded by the indexer.
The generated flat tables are used for reading data in the fronend. The backend still uses the EAV structure.

Catalog Search Index
You can search for products by many attribute values. Some of them may not be included in the flat tables generated by the flat indexer. This index fills in a table with the searchable attribute values for products so it's easier to look for them based on keywords. Having all the info in one table (or one field) makes it possible to use Full text search and get relevant results.

Product Prices.
The price of a product can be affected by many variables. For example, customer group, website, catalog discount rules.
Same as above, getting the products with their prices will mean a lot of joins or multiple selects. IN addition bundle products have a strange pricing system. This indexer aggregates the data in some tables (catalog_product_index_price_*) and makes the selects (sorting and filtering) much easier.

Catalog url Rewrites
This cleans up the url rewrite rules by setting which url corresponds to which product or category. It's easier this way for the url management internal system to decide which page should you view when calling a non-standard url. Instead of searching through all the product and categories URL keys it just searches in one table.

Category Products
In Magento you can set a category attribute named 'Is Anchor' to true or false. If it's true it means that the category in question will list all the products from it's child categories. Again, determining this realtime it will take more resources than just reading one table. This indexer creates the association between products and categories based on the associations you set in the backend and the 'Is Anchor' flag on the categories.

Stock Status
For simple products it's easy. They can be in stock or out of stock, but for configurable, grouped and bundle is not that easy. They can be in stock or out of stock depending on the child products associated to the main product. Again (I'm just repeating my self here) getting their status real time would mean a lot of queries.

Product Attributes.
This one collects all attributes that can be used in the layered navigation for same reason. Having all of them in one place for faster reading.

Tag Aggregation
I have no idea what this does. I've never used tags in a real live project.

Can't take credit for this as it is taken from original post at: http://stackoverflow.com/questions/4945307/can-someone-explain-magentos-indexing-feature-in-detail

Magento's indexing is only similar to database-level indexing in spirit. As Anton states, it is a process of denormalization to allow faster operation of a site. Let me try to explain some of the thoughts behind the Magento database structure and why it makes indexing necessary to operate at speed.

In a more "typical" MySQL database, a table for storing catalog products would be structured something like this:

PRODUCT:
    product_id INT
    sku        VARCHAR
    name       VARCHAR
    size       VARCHAR
    longdesc   VARCHAR
    shortdesc  VARCHAR
    ... etc ...

This is fast for retrieval, but it leaves a fundamental problem for a piece of eCommerce software: what do you do when you want to add more attributes? What if you sell toys, and rather than a size column, you need age_range? Well, you could add another column, but it should be clear that in a large store (think Walmart, for instance), this would result in rows that are 90% empty and attempting to maintenance new attributes is nigh impossible.

To combat this problem, Magento splits tables into smaller units. I don't want to recreate the entire EAV system in this answer, so please accept this simplified model:

PRODUCT:
    product_id INT
    sku        VARCHAR

PRODUCT_ATTRIBUTE_VALUES
    product_id   INT
    attribute_id INT
    value        MISC

PRODUCT_ATTRIBUTES
    attribute_id
    name

Now it's possible to add attributes at will by entering new values into product_attributes and then putting adjoining records into product_attribute_values. This is basically what Magento does (with a little more respect for datatypes than I've displayed here). In fact, now there's no reason for two products to have identical fields at all, so we can create entire product types with different sets of attributes!

However, this flexibility comes at a cost. If I want to find the color of a shirt in my system (a trivial example), I need to find:

1. The product_id of the item (in the product table)
2. The attribute_id for color (in the attribute table)
3. Finally, the actual value (in the attribute_values table)

Magento used to work like this, but it was dead slow. So, to allow better performance, they made a compromise: once the shop owner has defined the attributes they want, go ahead and generate the big table from the beginning. When something changes, nuke it from space and generate it over again. That way, data is stored primarily in our nice flexible format, but queried from a single table.

These resulting lookup tables are the Magento "indexes". When you re-index, you are blowing up the old table and generating it again.

Hope that clarifies things a bit!

Magento is a pretty powerful and complex system. It allows to work with massive amounts of data, but when database is overloaded with tons of records it becomes heavy and slow. Magento uses indexes to solve this problem. Indexes are additional database tables with some flat data, which allows to organize fast responses from the database.

By default, core system updates indexes on each item’s save. But in some cases you need to do it manually, for example some types of mass actions etc. You can update indexes any time from the admin backend (Admin->System->Index Management). But sometimes it causes problems.

For example, if you have 10k+ products and a lot of categories, rebuilding ‘catalog url rewrite‘ index may take hours. Then php script can just break because of max_execution_time exceeding. There is a way to solve several problems by running reindex process from the command line.