Деревья поиска хороши тем, что позволяют быстро осуществлять все основные операции: поиска, вставка, удаление. Деревьев есть много разных:
АВЛ,
красно-черные, различные вариации
B-деревьев и многие
другие.
Если мы храним в базе данных некоторые связанные данные (т.е. записи, состоящие из нескольких значений, возможно, различного типа), то можно выделить какое-то из этих значений (которое более-менее уникально характеризует запись или же мы будем часто ссылаться на эту запись по этому значению) в качестве ключа. Таким образом, зная ключ, пользователь нашей базы сможет достаточно быстро получить все данные, ассоциированные с ним.
Подробностей архитектуры баз данных и используемых структур я Вам не подскажу (да и они наверняка используют достижения науки, не рассказываемые в университетских курсах), но могу сказать следующее:
- Если Ваша база будет невелика — используйте красно-черное дерево (или АВЛ).
- Если база может быть большой — используйте B деревья (для случаев, когда все данные просто не влезут в память).
В каждом узле дерева Вы будете хранить помимо ключа, ссылок на детей и, возможно, некоторой вспомогательной информации для балансировки ещё и те дополнительные значения, которые могут быть ассоциированы с ключом.
Тип ключа, разумеется, совершенно неважен. Главное — возможность сравнивать ключи и определять, какой из двух меньше / больше.
Однако, я бы не очень назвал такое применение реальным проектом. В реальных проектах Вам редко придётся вручную реализовывать какую-либо структуру данных — всегда можно (и нужно) использовать существующие библиотеки.
