[Grulic-dev] estructura de datos para mantener ordenado

Tengo una tabla con 500.000 registros aproximadamente, y las quiero
indexar por nombre.
Pero el índice es especial, quiero hacerlo por palabra. Cada registro
tiene al menos 3 palabras, por lo tanto, cada registro me genera 3
entradas en el índice.
Luego busco por palabra consultando en ese índice.

Había pensado que lo mejor era un árbol binario balanceado, para tener
el mismo tiempo de búsqueda para todos los registros, pero resulta que
al armarlo se arrastra a partir del registro 100.000, aparentemente,
por tras del proceso de rebalancear el árbol cada vez.
El tiempo de armado se hace bastante largo a partir de ahí, y hace
inviable esperar.

¿Alguien sabe qué estructura de datos se puede usar?,
Necesito que sea eficiente al crear el índice y eficiente al acceder
los registros.

Trabajo en C++, y el índice lo armo en memoria.

gracias de antemano.

Saludos

Domingo Becker