В настоящее время я изучаю дерево Log-Structured-Merge, описанное O'Neil et.и др.Что-то мне не совсем понятно относительно худшей сложности поиска в дереве LSM.Компоненты, находящиеся на дисковом пространстве, хранят свои данные в B-дереве, верно?
Как указано в документе:
Как правило, чтобы гарантировать, что все записи вLSM-дерево было изучено, необходимо, чтобы поиск с точным соответствием или поиск по диапазону имел доступ к каждому компоненту (C_n) через его структуру индекса.
Это указывает на то, что поиск через CnКомпоненты, находящиеся в дисковом пространстве, в худшем случае - O (n).
Но это только обход компонентов, а не прохождение внутри компонента через пары ключ-значение.Поскольку пары ключ-значение хранятся в B-дереве, которое в виде сложности поиска O (log n), означает ли это, что поиск в дереве LSM имеет сложность O (n log n)?