David McCusker writes about his preference for early optimization on the OSAF dev list. As I wrote here a while ago, this is also my preference. The pitfall in delaying optimization is that once you have implemented some software there is not necessarily a direct path to an optimized version. Typically a re-design or at least a significant amount of backtracking is required.
Sometimes it is obvious how optimization can be applied later on, in which case an unoptimized implementation can be traded off in the short term against delivering something more quickly, but it is always risky to assume that once something has been developed optimization will only require localised changes to the code. As for the point of view that significant bottlenecks can only be determined after implementation, I'd say the ability to foresee issues like this is why experienced developers are paid more (or should be paid more).
In the same posting he goes on to discuss performance of btrees. My IndexedBtree class both stores keys in inner nodes and rebalances on deletion when required. The performance advantage of the former is obvious, that of the latter not so clear one way or the other.