геометрический поиск в красном черном бинарном дереве поиска

Я в настоящее время реализую красно-черное двоичное дерево поиска для геометрического поиска интервала.
Я сохраняю сегменты дерева, содержащие начальную точку и конечную точку, где начальная точка является ключевой записью в дереве.
Моя задача заключается в том, чтобы иметь возможность сохранять в сегменты дерева, которые имеют повторяющуюся начальную точку (или, если хотите, с тем же ключом).
Это своего рода мультикарта C ++ для геометрического поиска.
Решение, которое я придумал: для каждой записи, у которой есть дубликаты ключей, сохраните список (или вектор) сегментов с соответствующими дубликатами ключей.
Проблемы, которые я вижу с этим подходом, имеют две стороны:
1. Это снизит эффективность поиска при наличии большого количества дубликатов ключей.
2. Мне придется использовать больше памяти для хранения дубликатов ключей.

Мой вопрос: есть ли другой способ реализовать это более эффективно?