When a LINQ expression directly targets a database, the DLINQ provider has full access to the database's indexes. But LINQ is not only about databases, it can also target XML or even simple object collections. For larger queries, the lack of indexing may become an issue.
In order to address the issue, Aaron Erickson has created a product called Index for Objects or i4o. This project, which is open source, is downright trivial to use. One merely has to add an Indexable attribute to properties that should be indexed. When the objects are subsequently placed in an IndexableCollection, the indexes are automatically generated.
The magic occurs at runtime when calls to the Where and Join extension methods are made. i4o evaluates the expression tree and, if appropriate, replaces the for-each loops with an index lookup.
This technique may end up only being applicable when using very large, in memory object collections. In tests against collections of 1 million objects, i4o resulted in speed improvements of roughly two orders of magnitude.
Being a new project, there are still pending issues. Some are trivial and will be done soon, like adding support for removing objects from collections or supporting BindingList. The harder ones include how to handle updates to objects in an indexed collection. The objects do not 'know' they are in a collection, adding support for INotifyPropertyChanged to every indexed class is tedious, and it probably is not possible to use some sort of Aspect Orientated Programming technique to inject the necessary event hooks.
The project in binary and source code format can be downloaded from CodePlex. For more information about i4o, or to make suggestions for future enhancements, you can read Aaron Erickson's blog.