WARNING!
Only do the following on a unmounted filesystem and make sure the filesystems you are going to alter are cleanly unmounted before tuning them with the tune2fs or e2fsck utilities. (Boot from a LiveCD such as Knoppix if you need to.) Altering or tuning a filesystem while it is mounted can cause severe corruption! You have been warned!

Using Directory Indexing

This feature improves file access in large directories or directories containing many files by using hashed binary trees to store the directory information. It’s perfectly safe to use, and it provides a fairly substantial improvement in most cases; so it’s a good idea to enable it:

# umount /dev/hdX
# fsck.ext3 /dev/hdX
# tune2fs -O dir_index /dev/hdX

Since this only takes effect with directories created on that filesystem after tune2fs is run, ut is in order to apply this to currently existing directories. Run the e2fsck utility to optimize and reindex the directories on the filesystem

# e2fsck -D -f /dev/hdX

Change this to reflect your settings.

Note:
This should work with both ext2 and ext3 filesystems.
Depending on the size of your filesystem, this could take a long time.