Indexing Strategy

I have a bit of a problem with regards an indexing strategy. Well,
basically there is no indexing strategy on a set of data I have at
work. Now, I didn't create the design as I would have allowed for this.

OK, so there is primary key (clustered) indexes (mainly composite
keys), but no other indexes on the tables. As you would expect, the
performance leaves a lot to be desired. A hell of a lot. We have
several million rows in a lot of the tables. None of the queries seem
to be overly complex so we can work through the applications at a later
stage.

We have multiple copies (one per client per country) of the same
structure (I may have considered combining these to allow better
performance). One specific SP that I need to run takes 40+ hours
without indexes and 5 hours with some (130) basic indexes to get us
started on a better design. These 130 indexes are the minimum I suspect
we need and from there, we can start to work out which ones we need.

Now the test database (our worst performer) doubles in size to 20Gb,
but the performance is much much better (as expected). The original
thinking behind the design was for storage concerns (server space
recently upgraded) and for performance with bulk inserts.

We have a lot of bulk inserts, but I suspect that these are not too
bad, and the time taken for indexing these is negligable due to the
performance gains. I strongly suspect that we have a considerable
amount of table scans going on, but the problem is that people here
don't understand indexing (yet) or have the time (probably because it's
all taken up using the poorly designed system). That's a whole seperate
issue for me to address.

So, finally getting round to my questions...

Is there any good reference explaining in Layman's terms why you need
basic (or advanced) indexing ? Any links would be appreciated. I need
this to help explain to colleagues why a disk space increase and
indexing will be far better than spending thousands on a new box and
doing the same (a common problem I suspect).

How can I accurately estimate the amount of time taken to update an
index once data is bulk inserted. I don't want to re-index from scratch
as this may take too long. Indexing my database first time round takes
about 1 hour 30 minutes.

It's all part of an ongoing bit of digging into the system and re-doing
it to make it work properly. I'm sure most of you will have been there
at some point or another.

Thanks


Ryan