Структура данных BST была реализована
Структура данных BST была реализована в качестве возможной структуры данных для индексов в СУБД Sedna. Существует ещё много возможностей её оптимизации (в основном, алгоритмов разделения), которые необходимо дополнительно рассмотреть в будущем. В настоящее время проводится достаточно много работ, связанных с использованием префиксных деревьев.
Различные эксперименты с разными наборами данных подтверждают, что структура данных BST показывает производительность не хуже, чем у B-деревьев. Поэтому она может использоваться как полная их замена для строковых ключей. При этом, в случае, если строки достаточно длинные и по своей природе могут иметь длинные общие префиксы, можно достичь значительного сжатия индекса. Например, значительного выигрыша можно достичь при хранении индекса по нумерующим числам в XML-документах и быстрого поиска по ним, например для поддержки блокировок .
Однако стоит отметить, что реализация BST достаточно сложна, и при выборе структуры данных для каких-то задач в общем случае есть смысл использовать более проверенные и надёжные реализации B-деревьев.
