One of my standard pagination actions in my CMS is to show the alphabetical quick access bar when sorting by alpha column. For example, if the results are sorted by name, in the pagination section, I display a series of links, from A to Z, so that you immediately get to the page for a specific first character.
Example: 
I'm currently doing this, getting all the results for this column, sorted alphabetically, and then scrolling all of them in PHP and writing down which page the record appears on. This works great when you are dealing with only a few hundred results, but now I am working on a project that could potentially have several hundred thousand lines, and this is simply not a viable option.
Is there a more efficient method to create such an index? Note that it should also handle more than just AZ, since lines can start with numbers or punctuation marks.
Edit for clarification : I'm not looking for a simple list of all the first characters, which is easy. I need to calculate on which page from the final results the field starting with this symbol will be included. So say we are looking for someone named Walter, and I have 1000 rows, I need to know where W. starts in this 1-1000 range.
Chipersoft
source share