0

アプリケーションのスケールアップに問題があり、ここで質問することにしました。

リレーショナルデータベース（たとえばmysql）について考えてみます。ユーザーが投稿を作成できるようにし、これらがpostテーブルに保存されているとします（フィールドは:) postid, posterid, data, timestamp。したがって、最新性で並べ替えてすべての投稿を取得する場合は、とを使用してすべての投稿を取得するだけposterid = youですorder by date。十分に単純です。

このプロセスでは、カーディナリティが最も高いため、インデックスとしてタイムスタンプが使用されます。したがって、インデックスを調べるだけでなく、このタスクを完了するには、文字通りディスクから1行フェッチする必要があります。素晴らしい！

ただし、最後に投稿してから、他のユーザーによる（システム内の）投稿が100万回増えたとします。次に、最新の投稿を取得するために、データベースはタイムスタンプにインデックスを再度ペグしますが、それ以降に発生した投稿の数がわからない場合（または、少なくとも手動で優先キーを推定して設定する必要があります）？次に、1行をフェッチするためだけに、 100万行と1行を調べるのに無駄がありました。

さらに、複数の任意のユーザーからの一連の投稿がユースケースの1つになるため、userid_timestampのようなフィールドを作成してサブインデックスを作成することはできません。

私はこれを間違って見ていますか？または、そのような操作を少なくともある程度効率的に実行できるようにするために、アプリケーションから根本的に何を変更する必要がありますか？

4

3 に答える 3

3

インデックス作成

クエリがある場合： 、 {posterid、timestamp}... WHERE posterid = you ORDER BY timestamp [DESC]の複合インデックスが必要です。

  • 特定のユーザーのすべての投稿を検索するには、インデックスのリーディングエッジ（posterid）で範囲スキャンを実行します。
  • ユーザーの最も古い/最新の投稿の検索は、単一のインデックスシークで実行できます。これは、Bツリーの高さに比例します。log（N）に比例します。ここで、Nはインデックス付けされた行の数です。

その理由を理解するには、SQLインデックスの構造を見てください。

クラスタリング

「通常の」Bツリーインデックスのリーフは、インデックス付きの行への「ポインタ」（物理アドレス）を保持しますが、行自体は「テーブルヒープ」と呼ばれる別のデータ構造に存在します。ヒープは、クラスタリングと呼ばれるBツリーのリーフに行を直接格納することで削除できます。これには長所と短所がありますが、主要な種類のクエリが1つある場合は、クラスタリングによってテーブルヒープアクセスを排除することを検討する必要があります。

この特定のケースでは、テーブルは次のように作成できます。

CREATE TABLE T (
    posterid int,
    `timestamp` DATETIME,
    data VARCHAR(50),
    PRIMARY KEY (posterid, `timestamp`)
);

MySQL / InnoDBはすべてのテーブルをクラスター化し、クラスター化キーとして主キーを使用します。postidクラスタ化されたテーブルのセカンダリインデックスは高額になる可能性があり、すでに自然キーがあるため、代理キー（）は使用していません。代理キーが本当に必要な場合は、代理キーを作成し、自然キーを介してクラスタリングを確立しておくことを検討してください。

于 2012-12-25T16:46:26.227 に答える
1

次のようなクエリの場合

where posterid = 5
order by timestamp

また

where posterid in (4, 578, 222299, ...etc...)
order by timestamp

インデックスを作成する(posterid, timestamp)と、データベースはそれをすべて単独で選択する必要があります。

編集-私はちょうどmysqlでこれを試しました

CREATE TABLE `posts` (
    `id` INT(11) NOT NULL,
    `ts` INT NOT NULL,
    `data` VARCHAR(100) NULL DEFAULT NULL,
    INDEX `id_ts` (`id`, `ts`),
    INDEX `id` (`id`),
    INDEX `ts` (`ts`),
    INDEX `ts_id` (`ts`, `id`)
)
ENGINE=InnoDB

たくさんのデータを入れて、

explain
select * from posts where id = 5 order by ts

id_tsインデックスを選択します

于 2012-12-25T16:35:55.153 に答える
0

ハッシュテーブルを使用してデータベースを実装すると仮定します-はい。ハッシュテーブルは順序付けられておらず、最大値を見つけるためにすべての要素を反復する以外に方法はありません。

ただし、B +ツリー（実際にはディスク、つまりデータベース用にかなり最適化されている）などの順序付けられたDSを使用する場合は、話が異なります。

ユーザー（一次コンパレータ/コンパレータ）と日付（二次コンパレータ、降順）で並べ替えられたB+ツリーに要素を格納できます。このDSを入手したらO(log(n))、主要な基準（user-id）に一致する最初の要素を見つけることにより、ディスクシークで最初の要素を見つけることができます。

私はデータベースの実装に精通していませんが、AFAIKでは、B +ツリーに基づいてインデックスを作成できるものもあります。そうすることで、ユーザーの最後の投稿をより効率的に見つけることができます。

PS

正確には、「最大」要素または順序付けの概念は、関係代数では十分に定義されていません。max演算子はありません。R単一の列を持つテーブルの最大要素を取得するには、a実際にそのテーブルのデカルト積を作成し、このエントリを見つける必要があります。厳密な関係代数にはmax演算子もsort演算子もありません（SQLには存在しますが）

(Assuming set, and not multiset semantics):
MAX = R \ Project(Select(R x R, R1.a < R2.a),R1.a)
于 2012-12-25T15:31:13.120 に答える