Tries \'equilibr\'es et compacts

Les tries \'equilibr\'es et compacts fournissent une structure adapt\'ee aux index ordonn\'es en g\'en\'eral, et plus particuli\`erement aux index ordonn\'es des bases de donn\'ees m\'emoire. Appliqu\'ee \`a des donn\'ees typiques du langage anglais, cette structure n'utilise que 2 octets par cl\'e. La compression est obtenue au moyen d'une repr\'esentation compacte par bit-map de tries ou de sous-tries. La structure globale regroupant des sous-tries en noeuds de type blocs est similaire \`a un arbre$-B$ (arbre $n$-aire \'equilibr\'e). Toutes les propri\'et\'es des arbres$-B$ sont conserv\'ees, en particulier celle de pouvoir faire des \'equilibrages de charge entre des noeuds fr\`eres.