67

リンクリストをMySQLデータベースに保存して、挿入が簡単になり（つまり、毎回たくさんのインデックスを再作成する必要がない）、リストを順番に簡単に引き出すことができるようにするための最良の方法は何ですか？

4

13 に答える 13

18

2つの自己参照列PreviousIDとNextIDを持つテーブルを作成します。アイテムがリストの最初のものである場合、PreviousIDはnullになり、最後である場合、NextIDはnullになります。SQLは次のようになります。

create table tblDummy
{
     PKColumn     int     not null, 
     PreviousID     int     null, 
     DataColumn1     varchar(50)     not null, 
     DataColumn2     varchar(50)     not null,  
     DataColumn3     varchar(50)     not null, 
     DataColumn4     varchar(50)     not null, 
     DataColumn5     varchar(50)     not null, 
     DataColumn6     varchar(50)     not null, 
     DataColumn7     varchar(50)     not null, 
     NextID     int     null
}
于 2008-09-15T18:12:39.793 に答える
17

エイドリアンのソリューションを使用しますが、1ずつインクリメントする代わりに、10ずつ、さらには100ずつインクリメントします。挿入は、挿入の下のすべてを更新しなくても、挿入しているものの差の半分で計算できます。平均挿入数を処理するのに十分な数を選択します。小さすぎる場合は、挿入中にすべての行をより高い位置に更新するようにフォールバックする必要があります。

于 2008-09-15T18:11:36.893 に答える
15

「位置」と呼ばれるテーブルに整数列を保存します。リストの最初の項目には 0、2 番目の項目には 1 などを記録します。データベースでその列にインデックスを付け、値を引き出したい場合は、その列で並べ替えます。

 alter table linked_list add column position integer not null default 0;
 alter table linked_list add index position_index (position);
 select * from linked_list order by position;

インデックス 3 に値を挿入するには、3 行目以降の位置を変更してから、次のように挿入します。

 update linked_list set position = position + 1 where position >= 3;
 insert into linked_list (my_value, position) values ("new value", 3);
于 2008-09-15T18:06:31.790 に答える
4

リンクリストは、テーブル内の再帰ポインタを使用して保存できます。これは、SQLに格納されている階層とほとんど同じであり、再帰的な関連付けパターンを使用しています。

詳細については、こちら（Wayback Machineリンク）をご覧ください。

これがお役に立てば幸いです。

于 2008-09-15T18:11:56.100 に答える
3

最も簡単なオプションは、リスト アイテムごとに行、アイテムの位置の列、およびアイテム内の他のデータの列を含むテーブルを作成することです。次に、位置列で ORDER BY を使用して、目的の順序で取得できます。

create table linked_list
(   list_id   integer not null
,   position  integer not null 
,   data      varchar(100) not null
);
alter table linked_list add primary key ( list_id, position );

リストを操作するには、位置を更新してから、必要に応じてレコードを挿入/削除します。リスト 1 のインデックス 3 に項目を挿入するには、次のようにします。

begin transaction;

update linked_list set position = position + 1 where position >= 3 and list_id = 1;

insert into linked_list (list_id, position, data)
values (1, 3, "some data");

commit;

リストの操作には複数のコマンドが必要になる場合があるため (たとえば、挿入には INSERT と UPDATE が必要です)、常にトランザクション内でコマンドを実行するようにしてください。

この単純なオプションのバリエーションとして、項目ごとにある係数 (100 など) で位置をインクリメントする方法があります。これにより、INSERT を実行するときに、後続の要素の位置を常に再番号付けする必要がなくなります。ただし、これには、次の要素をいつインクリメントするかを判断するためのもう少しの努力が必要になるため、単純さは失われますが、多くの挿入がある場合はパフォーマンスが向上します。

要件に応じて、次のような他のオプションが魅力的です。

  • リストに対して多くの操作を実行し、多くの検索を実行したくない場合は、位置列を使用する代わりに、リスト内の次の項目を指す ID 列を使用することをお勧めします。次に、アイテムを順番に取得するために、リストの取得でロジックを反復する必要があります。これは、ストアド プロシージャで比較的簡単に実装できます。

  • 多数のリストがあり、リストをテキスト/バイナリにシリアライズおよびデシリアライズする簡単な方法で、リスト全体のみを格納および取得する場合は、リスト全体を単一の値として単一の列に格納します。おそらくあなたがここで求めているものではないでしょう。

于 2008-09-15T18:16:04.280 に答える
2

すぐに思いつくアプローチがいくつかありますが、それぞれ複雑さと柔軟性のレベルが異なります。あなたの目標は、実際のリンクされたリストとしてストレージを必要とするのではなく、検索時に順序を保持することだと思います。

最も簡単な方法は、テーブル内の各レコードに序数値を割り当てることです (例: 1、2、3、...)。次に、レコードを取得するときに、序数列に order-by を指定して、順序を戻します。

このアプローチでは、リストのメンバーシップに関係なくレコードを取得することもできますが、1 つのリストのメンバーシップのみが許可され、レコードが属するリストを示す追加の「リスト ID」列が必要になる場合があります。

もう少し精巧で柔軟なアプローチは、メンバーシップに関する情報をリストに格納するか、別のテーブルにリストを格納することです。このテーブルには、リスト ID、序数値、およびデータ レコードへの外部キー ポインターの 3 つの列が必要です。このアプローチでは、基になるデータはリスト内のメンバーシップについて何も知らず、複数のリストに簡単に含めることができます。

于 2008-09-15T18:27:36.873 に答える
2

この投稿は古いですが、まだ 0.02 ドルを寄付します。テーブルまたはレコード セット内のすべてのレコードを更新するのは、順序付けを解決するのがおかしいように思えます。インデックス作成の量もクレイジーですが、ほとんどの人がそれを受け入れているようです。

更新とインデックス作成を減らすために私が思いついたクレイジーな解決策は、2 つのテーブルを作成することです (ほとんどの場合、すべてのレコードを 1 つのテーブルだけに並べ替えることはありません)。ソートされるリストのレコードを保持するテーブル A と、順序のレコードをグループ化して文字列として保持するテーブル B。順序文字列は、Web サーバーまたは Web ページ アプリケーションのブラウザー レイヤーで選択されたレコードを並べ替えるために使用できる配列を表します。 

Create Table A{
Id int primary key identity(1,1),
Data varchar(10) not null
B_Id int
}

Create Table B{
Id int primary key Identity(1,1),
GroupName varchat(10) not null,
Order varchar(max) null
}

注文文字列の形式は、ID、位置、および文字列を split() するための区切り文字である必要があります。jQuery UI の場合、.sortable('serialize') 関数は、リスト内の各レコードの ID と位置を含む POST フレンドリーな順序文字列を出力します。

本当の魔法は、保存された順序付け文字列を使用して、選択したリストを並べ替える方法です。これは、構築しているアプリケーションによって異なります。アイテムのリストを並べ替える jQuery の例を次に示します: http://ovisdevelopment.com/oramincite/?p=155

于 2014-01-10T07:35:58.967 に答える
2

https://dba.stackexchange.com/questions/46238/linked-list-in-sql-and-treesは、高速な挿入と順序付けのために浮動小数点位置列を使用するトリックを提案しています。

また、特殊な SQL Server 2014 hierarchyid機能についても言及しています。

于 2014-09-18T09:10:15.900 に答える
0

Datetimetype の created 列と の position 列を追加する方がはるかに簡単だと思うintので、select ステートメントで position を使用してorder bydesc オプションを作成すると、リストが順番に取得されます。

于 2011-08-11T12:34:23.980 に答える
-1

リストは、列にオフセット (リストのインデックス位置) を含めることで格納できます。中央の挿入は、新しい親の上にすべてインクリメントしてから挿入を行います。

于 2008-09-15T18:05:46.673 に答える
-1

高速なプッシュ/ポップ/削除 (元の値がわかっている場合) と検索をサポートする両端キュー (deque) のように実装すると、2 つのデータ構造が得られます。1 つは実際のデータ、もう 1 つはキーの履歴に追加された要素の数です。トレードオフ: この方法は、リンクされたリスト O(n) の途中に挿入すると遅くなります。

create table queue (
    primary_key,
    queue_key
    ordinal,
    data
)

queue_key+ordinal にインデックスがあります

また、キューに追加された行の数を格納する別のテーブルもあります...

create table queue_addcount (
    primary_key,
    add_count
)

新しいアイテムをキューのどちらかの端 (左または右) にプッシュするときは、常に add_count をインクリメントします。

後ろに押すと、序数を設定できます...

ordinal = add_count + 1

前に押すと、序数を設定できます...

ordinal = -(add_count + 1)

アップデート

add_count = add_count + 1

このようにして、キュー/リストのどこでも削除でき、順序どおりに戻り、順序を維持して新しいアイテムをプッシュし続けることもできます。

多数の削除が発生した場合、必要に応じて序数を書き直して、オーバーフローを回避できます。

リストの高速な順序付けされた取得をサポートするために、序数にインデックスを設定することもできます。

途中への挿入をサポートしたい場合は、挿入する必要がある序数を見つけて、その序数で挿入する必要があります。次に、その挿入ポイントに続いて、すべての序数を 1 ずつ増やします。また、通常どおり add_count をインクリメントします。序数が負の場合、以前の序数をすべてデクリメントして、更新を少なくすることができます。これは O(n) になります

于 2020-07-31T19:42:11.613 に答える