Then we created a second, lookup table with a primary key on a surrogate key and a unique index on a natural key. From there we replaced numerous columns in the original table with an "Id" column from the lookup table, enforced with a Foreign Key constraint.
This significantly reduced the size of the original table, saving precious memory space in the buffer cache and speeding up reads & writes to the table.
2/X