B-Tree indexes perform just fine on datetime fields. Were you using hash or inverted indexes maybe?