任意の順番で途中にレコードを追加できるデータベース設計

Question

現在、サービスを作っており、それぞれのレコードの順番が大切なのですが途中に新しいレコードが入る事が想定され、データベース設計が思いつきません。

id	text	created
1	こんにちは	2016/12/11
2	私の名前は太郎です	2016/12/12
3	どうぞよろしくお願いします。	2016/12/13

このようなテーブルがあった時に、

id	text	created
1	こんにちは	2016/12/11

と、

id	text	created
2	私の名前は太郎です	2016/12/12

の間に新たにレコードを挿入したい時、どのように設計、ソートすれば良いでしょうか・・・

id	text	created	sort
1	こんにちは	2016/12/11	1
4	はじめまして	2016/12/13	2
2	私の名前は太郎です	2016/12/12	3
3	どうぞよろしくお願いします。	2016/12/13	4

こんな事も考えましたが１つレコードの更新があるたびに結局は全レコードのsortを更新しなければなりません。

id	text	created	sort
1	こんにちは	2016/12/11	1
4	はじめまして	2016/12/13	1.5
6	それにしても、	2016/12/14	1.625
5	今日は寒いですね	2016/12/14	1.75
2	私の名前は太郎です	2016/12/12	2
3	どうぞよろしくお願いします。	2016/12/13	3

※日本語が崩壊しているのは気にしないでください笑

前後のレコードのsort平均値をセットしてソート、現実的そうですが何かとても気持ち悪いです。
何か良いアイデアがあればよろしくお願いします。

Answer 1

１つレコードの更新があるたびに結局は全レコードのsortを更新しなければなりません。

RDBMSというものの本質を考えると、そういう手段しかないと思います。RDBMSは、関係代数や関係論理に基づいた集合を扱うシステムですので、データそのものに「順番付け」はありません。別に管理するしかない、ということになります。

RDBMS以外の体系だと、順番を守って追加削除したい場合、「連結リスト」として保管するというような方法も考えられますが、RDBMSのシステムとは全く相容れません。

Comments

[kou0179]

なるほど、、、
処理は重くなりそうですが、別にインデックス配列で管理しようと思います。

[
[8],
[1],
[3],
[2],
[5],
[7]
]

こんな感じで・・・回答ありがとうございました。

Answer 2

途中に新しいレコードが入る

頻度やレコード数にもよりますが、以下のようにすれば、比較的シンプルに実装できると思います。

mysql> CREATE TABLE test (
    ->   id int PRIMARY KEY AUTO_INCREMENT,
    ->   text text,
    ->   created DATE,
    ->   sort int NOT NULL UNIQUE KEY
    -> );
Query OK, 0 rows affected (0.05 sec)

mysql> INSERT INTO test (text, created, sort) VALUES
    -> ('こんにちは', '2016-12-11', 1),
    -> ('私の名前は太郎です', '2016-12-12', 2),
    -> ('どうぞよろしくお願いします。', '2016-12-13', 3);
Query OK, 3 rows affected (0.04 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> SELECT * FROM test ORDER BY sort;
+----+--------------------------------------------+------------+------+
| id | text                                       | created    | sort |
+----+--------------------------------------------+------------+------+
|  1 | こんにちは                                 | 2016-12-11 |    1 |
|  2 | 私の名前は太郎です                         | 2016-12-12 |    2 |
|  3 | どうぞよろしくお願いします。               | 2016-12-13 |    3 |
+----+--------------------------------------------+------------+------+
3 rows in set (0.00 sec)


# ココからが「新たにレコードを挿入」する処理
mysql> BEGIN;
Query OK, 0 rows affected (0.00 sec)

## 挿入したい箇所の"sort"値を取得。
## データの不整合を防ぐため、SELECT ... FOR UPDATE 構文を使用する。
## https://dev.mysql.com/doc/refman/5.6/ja/innodb-locking-reads.html
mysql> SELECT sort FROM test WHERE text = '私の名前は太郎です' FOR UPDATE;
+------+
| sort |
+------+
|    2 |
+------+
1 row in set (0.01 sec)

mysql> UPDATE test SET sort = sort + 1 WHERE sort >= 2 ORDER BY sort DESC;
Query OK, 2 rows affected (0.02 sec)
Rows matched: 2  Changed: 2  Warnings: 0

mysql> INSERT INTO test (text, created, sort) VALUES
    -> ('はじめまして', '2016-12-13', 2);
Query OK, 1 row affected (0.00 sec)

mysql> COMMIT;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT * FROM test ORDER BY sort;
+----+--------------------------------------------+------------+------+
| id | text                                       | created    | sort |
+----+--------------------------------------------+------------+------+
|  1 | こんにちは                                 | 2016-12-11 |    1 |
|  4 | はじめまして                               | 2016-12-13 |    2 |
|  2 | 私の名前は太郎です                         | 2016-12-12 |    3 |
|  3 | どうぞよろしくお願いします。               | 2016-12-13 |    4 |
+----+--------------------------------------------+------------+------+
4 rows in set (0.00 sec)

sortカラムに（ユニーク）インデックスを張っておけば、ソートによって処理が重くなるようなことも無いはずです。
https://dev.mysql.com/doc/refman/5.6/ja/order-by-optimization.html

---

また、MySQL をお使いであれば、maisumakun様の回答にある通り

「連結リスト」として保管する

方法は難易度が高いと思われます。

連結リストは「再帰クエリ」(recursive query)と呼ぶ機能があると簡単に実現できますが、
MySQL は再帰クエリを実装しておらず、ストアドプロシージャを使用する必要があるらしいからです。
https://en.wikipedia.org/wiki/Hierarchical_and_recursive_queries_in_SQL

Though MySQL does not support common table expressions there exists a demonstration of WITH RECURSIVE emulation[17] using stored procedures.

以下追記

「obj」カラムと「sort」カラム、この２つを合わせてユニークキーになる

であれば、そのようにユニークインデックスを作成してやればよいです。
で、SELECT, UPDATE, INSERT する際にも obj カラムの値を指定してやれば、単一テーブルで実現できます。

mysql> CREATE TABLE test (
    ->   id int PRIMARY KEY AUTO_INCREMENT,
    ->   text text,
    ->   created DATE,
    ->   obj int NOT NULL,
    ->   sort int NOT NULL,
    ->   UNIQUE KEY (obj, sort)
    -> );
Query OK, 0 rows affected (0.04 sec)

mysql> INSERT INTO test (text, created, obj, sort) VALUES
    ->   ('こんにちは', '2016-12-11', 1, 1),
    ->   ('私の名前は太郎です', '2016-12-12', 1, 2),
    ->   ('どうぞよろしくお願いします。', '2016-12-13', 1, 3),
    ->   ('こんばんは', '2016-12-11', 2, 1),
    ->   ('私の名前は花子です', '2016-12-12', 2, 2),
    ->   ('どうぞよろしくお願いします。', '2016-12-13', 2, 3);
Query OK, 6 rows affected (0.01 sec)
Records: 6  Duplicates: 0  Warnings: 0

mysql> SELECT * FROM test ORDER BY obj, sort;
+----+--------------------------------------------+------------+-----+------+
| id | text                                       | created    | obj | sort |
+----+--------------------------------------------+------------+-----+------+
|  1 | こんにちは                                 | 2016-12-11 |   1 |    1 |
|  2 | 私の名前は太郎です                         | 2016-12-12 |   1 |    2 |
|  3 | どうぞよろしくお願いします。               | 2016-12-13 |   1 |    3 |
|  4 | こんばんは                                 | 2016-12-11 |   2 |    1 |
|  5 | 私の名前は花子です                         | 2016-12-12 |   2 |    2 |
|  6 | どうぞよろしくお願いします。               | 2016-12-13 |   2 |    3 |
+----+--------------------------------------------+------------+-----+------+
6 rows in set (0.00 sec)

mysql> BEGIN;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT sort FROM test WHERE obj = 1 AND text = '私の名前は太郎です' FOR UPDATE;
+------+
| sort |
+------+
|    2 |
+------+
1 row in set (0.01 sec)

mysql> UPDATE test SET sort = sort + 1 WHERE obj = 1 AND sort >= 2 ORDER BY sort DESC;
Query OK, 2 rows affected (0.02 sec)
Rows matched: 2  Changed: 2  Warnings: 0

mysql> INSERT INTO test (text, created, obj, sort) VALUES
    ->   ('はじめまして', '2016-12-13', 1, 2);
Query OK, 1 row affected (0.00 sec)

mysql> COMMIT;
Query OK, 0 rows affected (0.01 sec)

mysql> SELECT * FROM test ORDER BY obj, sort;
+----+--------------------------------------------+------------+-----+------+
| id | text                                       | created    | obj | sort |
+----+--------------------------------------------+------------+-----+------+
|  1 | こんにちは                                 | 2016-12-11 |   1 |    1 |
|  7 | はじめまして                               | 2016-12-13 |   1 |    2 |
|  2 | 私の名前は太郎です                         | 2016-12-12 |   1 |    3 |
|  3 | どうぞよろしくお願いします。               | 2016-12-13 |   1 |    4 |
|  4 | こんばんは                                 | 2016-12-11 |   2 |    1 |
|  5 | 私の名前は花子です                         | 2016-12-12 |   2 |    2 |
|  6 | どうぞよろしくお願いします。               | 2016-12-13 |   2 |    3 |
+----+--------------------------------------------+------------+-----+------+
7 rows in set (0.00 sec)

Comments

[kou0179]

これが一番分かりやすく良さそうです。
ちょっと訳あってsortがユニークではないのですが、またsortテーブルなど作って対応はできそうです。
助かりました、ありがとうございます。

[KiyoshiMotoki]

返信ありがとうございます。

> sortテーブルなど作って対応はできそうです。

それでも可能ではありますが、若干、実装の難易度は上がりますよ。

テーブルを分割すると
　・片方のテーブルのロックし忘れによるデータ不整合
　・ロックを取得する順番を間違えたことによるデッドロック
が発生する可能性が生じますので。

> ちょっと訳あってsortがユニークではない

について詳しい状況を教えていただければ、何かアドバイスができるかも知れません。
（できないかも知れませんがw）

[kou0179]

>ちょっと訳あってsortがユニークではない
こちらが、１つのテーブルでいくつものオブジェクトを管理する予定で
「obj」カラムと「sort」カラム、この２つを合わせてユニークキーになるんです・・・
ですので、「obj」が異なる、同じ「sort」が複数存在してしまいます。
何かアイデアがあればお願い致します。

[kou0179]

いくつものオブジェクト>>レコードごとに属しているオブジェクトが違うもの

分かりにくかったので訂正いたします！

[KiyoshiMotoki]

回答欄に追記させていただきました。
確認願います。

Answer 3

IDとSORTとは別に、連結リスト形式と併用するのがいいかもしれません。
連結リスト