big-o - LSM ツリーのルックアップ時間

Question

単純な検索クエリ (単一のWHERE句のクエリなど) の場合、ログ構造のマージ ツリーで最悪の場合の時間の複雑さはどれくらいですか?

O(log N)ですか？O(N*Log N)? 他の何か？

WHEREキー値データベースで複数の句を 検索するような、複数のクエリの場合はどうですか?

LSM ツリーに関するウィキペディアのページには、現在この情報がありません。

そして、私は元の論文を理解しようとしています。