Outra ideia a tentar pode ser identificar strings comuns e representá-las com um bitmap. Por exemplo, tenha dois bits para representar o protocolo (http, https, ftp ou outro), outro bit para indicar se o domínio começa com "wwww", dois bits para indicar se o domínio termina com ".com", ". org", ".edu" ou qualquer outra coisa. Você teria que fazer alguma análise em seus dados e ver se eles fazem sentido e se existem outras strings comuns que você pode identificar.

Se você tiver muitos URLs para o mesmo site, considere dividir sua tabela em duas diferentes, uma contendo o domínio e a outra contendo o caminho relativo ao domínio (e a string de consulta e o ID do fragmento, se houver). Você teria uma tabela de links com o id do URL, o id do domínio e o id do caminho, e substituiria sua tabela de URLs original por uma visualização que unisse as três tabelas. A tabela de domínio não precisaria ser restrita ao domínio, você poderia incluir o máximo de URL que fosse comum (por exemplo, 'http://stackoverflow.com/questions'). Isso não exigiria muito código para implementar e tem a vantagem de ainda ser legível. Sua codificação numérica pode ser mais eficiente, uma vez que você a descubra, você terá que analisar seus dados para ver qual deles faz mais sentido.