データベースで使用されるインデックスメカニズムは、データベースに完全に依存しています。データベースについて具体的な質問がある場合は、データベースのドキュメントを参照してください。ほとんどのインデックスはBツリーであると思いますが、それは単なる推測です。
可変長文字列の格納に関する質問もデータベースエンジン次第です。一般に、これらは長さでエンコードされるため、最初の2バイトは文字列の長さに続き、文字が続きます。ただし、SQLには、ヌルバイトエンコーディング（Cで行われるように）などの他のメカニズムを妨げるものはありません。この方法でそれらを保存するデータベースがおそらくそこにあります。
ただし、これは概算です。MSSQLの長い文字列は、レコードの固定長フィールドとは別のデータページに格納されます。長い文字列がページサイズを超えると、文字列がページに収まらなければならないため、状況ははるかに複雑になります。
テキスト検索機能をサポートするデータベースには、文字列のインデックス作成のためのまったく異なるメカニズムがあります。通常は転置インデックスです。
問題を解決するための最良の方法を探している場合は、別の質問で問題を説明する必要があります。データベースの詳細をお探しの場合は、Google、データベースドキュメント、およびWikipediaが最適です。