There have been many articles (Discussions, posts, whatever) on how Visual FoxPro gets its speed from and how the VFP index actually works.
Calvin's most recent post,
What is an index anyway?, goes into full detail.
As a quick note on indexing and VFP 9, VFP 9 includes a new Binary index, useful for handling logical indices. The new BINARY index is smaller and also much faster.
INDEX ON DELETED() TAG DELETED BINARY
Example: Table with 8000 records (a few deleted)
INDEX ON DELETED() TAG DELETED : CDX file size was about 22K
INDEX ON DELETED() TAG DELETED BINARY: CDX file was only 4 K
There used to be a time when almost every application created an index for DELETED() until Chris Probst (referenced here on ProFox - I would link to the entire article but FoxPro advisor never put it online - hey Chris! did you know you could revise it and put it online yourself?) shattered the illusion that it would make things faster.
As it notes in the VFP9 help file, this new BINARY tag can be very helpful on networks or WANs where the old approach could cause performance problems.