>>936
まずファイルシステムの問題なのかJavaの問題なのか切り分けたら?
ext3->reiserfsに変えてみるとか
Java以外の言語でアクセスして測定してみるとか

>>937
CentOS4.4ならデフォルトでdir_indexが有効になる
それに1ディレクトリ1000個に分けても遅いってんだからdir_indexは関係ないだろ