並べ替えできるデータをデータベースに保存する方法

システム開発を行っているとよく、クライアントからデータを任意の順番に並び替えたいという要望があります。並び替えを実行するプログラムは、配列の順序を変えるだけなので簡単ですが、その順序をデータベースにどうやって保存するかという点についてはいつも迷ってしまいます。
これには色々なやり方がありますので、まとめてみました。

8つの方法

今回は8つの方法に分けてみましたが、いくつかの方法は組み合わせて使えると思いますし、さらに工夫した方法もあると思います。方法1～6は大きなくくりとしてよく見かけるものです。方法7方法8は私が考えたもので見たことがないし私自身も実装したことが無いのですが、飛躍したアイデアでもないので載せました。
対象のデータベースは主にRDBですが、KVSに向いているかどうかも（良い・普通・悪い）の3段階で書いています。
データ構造と使い方の説明は書いていますが、具体的な実装は書いていません。

システムによって変える必要がありますが、方法2と方法6を優先的に使っていく結論になりました。KVSでは方法6一択ではないかとさえ思います。

方法1 レコードに自身の順番を持たせる

おそらく最も広く用いられている方法かと思います。
次のようなテーブルで順序を保存します。

id	name	pos
#1	Cat	2
#2	Dog	1
#3	Rat	3

posカラムに1から順にレコードが何番目なのかを保存します。
日常世界でいうと、整理券を用いた方法と言えます。レコード自身に自分が何番目か分かる整理券を持たせます。
posカラムを昇順（小さい順）にソートするだけで順序を復元できるため、非常に扱いやすいです。SQLで一発です。posカラムの名称は他にも、index、order_number、sort_orderなどが用いられるようです。

実装の難易度　★★　易しい
KVSと相性　悪い

メリット

• 並び替えできるレコード数に上限が無い
• 1つのテーブルで完結する
• テーブルすべてを参照しなくても、あるレコードの自身の順番がわかる
• ドラッグ＆ドロップの並べ替えに適している

デメリット

• 順序の入れ替えやレコードの追加ときに多数のレコードを更新する必要がある
• レコードをオブジェクトと捉えたときに自身の順番はオブジェクトの属性ではない
• 1通りの順序しか保存できない

この方法のデメリットは、例えば3番目のレコードを1番目にしようとすると、そのレコードの順番だけでなく1番目だったレコードを2番目にして、2番目だったレコードを3番目にする必要があります。順序を入れ替えるたびにテーブル内の多くのレコードを更新する必要があるのです。

方法2 レコードに表示優先度を持たせる

データベースはReadよりもWriteの負荷が大きいため、なるべくWriteは減らしたいものです。
そこで、次のようなテーブルを用います。

id	name	priority
#1	Cat	50
#2	Dog	100
#3	Rat	0

表示優先度（priorityカラム）は高いほど先に表示されます。
priorityカラムを降順（大きい順）にソートするだけで順序を復元できます。ここで、#3を1番目にしたい場合は#3のpriorityを100よりも大きい数に設定するだけで可能です。
表示優先度の具体的な数値は名前とか年齢とかと同じようにユーザーに直接入力してもらいます。

方法1と違って、表示優先度が同じという可能性があるため、表示優先度が同じ場合にどのような順序で表示するか考える必要があります。

実装の難易度　★　非常に易しい
KVSと相性　普通

メリット

• 並び替えできるレコード数に上限が無い
• 1つのテーブルで完結する
• 順序の入れ替えやレコードの追加ときに多数のレコードを更新する必要が無い

デメリット

• テーブルすべてを参照しないと、あるレコードの自身の順番がわからない
• レコードをオブジェクトと捉えたときに表示優先度はオブジェクトの属性ではない
• 1通りの順序しか保存できない
• ドラッグ＆ドロップの並べ替えに適していない

この方法最大のデメリットは、表示優先度の数字をユーザーに直接入力してもらう必要があるため、ドラッグ＆ドロップの並べ替えが不可能だということです。しかし、方法1よりもさらに実装が簡単ですので、順番の並び替えが頻繁に発生しない場合には積極的に採用して良いと思います。

なお、ユーザーに直接入力してもらうのは表示優先度ではなく方法1と同様に自身の順番でもOKです。

方法3 レコードに自身の順番を浮動小数点数で持たせる

方法2と同じくWriteを減らして、方法2のデメリットであったドラッグ＆ドロップの並べ替えも可能にする方法です。
テーブルは次のようになります。

id	name	pos
#1	Cat	1.5
#2	Dog	1
#3	Rat	2

posカラムは方法1と同じくレコードの順番を保存しますが、浮動小数点数も用いることができます。
posカラムを昇順（小さい順）にソートするだけで順序を復元できます。ここで、#3を3番目から2番目にしたい場合は、#3のposを#1と#2のちょうど間の数にします。

$$\cfrac{1 + 1.5}{2} = 1.25$$

実装の難易度　★★★★★　非常に難しい
KVSと相性　普通

メリット

• 並び替えできるレコード数に上限が無い
• 1つのテーブルで完結する
• 順序の入れ替えやレコードの追加ときに多数のレコードを更新する必要が無い
• ドラッグ＆ドロップの並べ替えに適している

デメリット

• テーブルすべてを参照しないと、あるレコードの自身の順番がわからない
• レコードをオブジェクトと捉えたときに自身の順番はオブジェクトの属性ではない
• 1通りの順序しか保存できない

この方法は一見簡単そうですが、非常に実装が難しいです。
例えば初めてレコードを追加するときのposの値や、レコードが2つしかないときに並べ替えるにはどうするか、ドラッグ＆ドロップしたときにいつデータベースに書き込むかなど、その他にも考えなければならないことが多くあります。安易に手を出すべきではありません。

さて、この方法は並び替えや挿入を何度も繰り返すと限界が来て、並び替えられなくなります。私の検証ではposの間隔を1ずつにして1,075回でした。

$$\cfrac{1 + 0}{2} = 0.5$$

$$\cfrac{0.5 + 0}{2} = 0.25$$

$$...$$

を繰り返すと、1,075回で浮動小数点数（double型）で表せなくなり答えが0になるのです。

そのため、ときどきposを振りなおす必要があります。例えばposの差があらかじめ決めておいた値を下回った時です。ただし、1,075回はあくまで最短ですので、振りなおしのプログラムが動くケースは少ないでしょう。

ちなみにposの間隔を1ずつではなく、浮動小数点数の範囲で1/2になるようにとると操作回数が最短2,098回まで増えますが、末尾へのレコード追加が2,098回連続で発生すると限界となりますので、1ずつのようにposの間隔は固定するのがベストと考えられます。

浮動小数点数を使う他の問題点として、ソートの計算コストが整数に比べて高いことがあります。ソートにかかる時間とCPU負荷が高くなるので、レコード数が多くなると整数の場合と比べて差が出てくる可能性があります。浮動小数点数を使いたくない場合は次の方法4を用いることになります。

方法4 レコードに自身の順番を大きな整数で持たせる

方法3で浮動小数点数だと計算コストに不安がある場合、浮動小数点数ではなく十分に大きな整数を用いることで、方法3と同じプログラムを浮動小数点数を使わずに動かすことができます。
テーブルは次のようになります。

id	name	pos
#1	Cat	1500000
#2	Dog	1000000
#3	Rat	2000000

posカラムはレコードの順番を保存しますが、浮動小数点数の代わりに十分に大きな数を用います。
posカラムを昇順にソートするだけで順序を復元できます。ここで、#3を3番目から2番目にしたい場合は、#3のposを#1と#2の中間の値にします。

$$\cfrac{1000000 + 1500000}{2} = 1250000$$

さて、この方法も並び替えに限界があります。しかも、1/2ずつ数が減っていきますので、たった数十回同じ操作を繰り返すだけで限界が来ます。
浮動小数点数の方法3が1,075回だったのに対してこちらはposをMySQLのBIGINTの範囲で1/2になるように割り当てても最短63回の操作でposが重複します。振りなおしのプログラムは頻繁に動くことになるでしょう。

実装の難易度　★★★★★　非常に難しい
KVSと相性　普通

メリット

• 並び替えできるレコード数に上限が無い
• 1つのテーブルで完結する
• 順序の入れ替えやレコードの追加ときに多数のレコードを更新する必要が無い△
• ドラッグ＆ドロップの並べ替えに適している

デメリット

• テーブルすべてを参照しないと、あるレコードの自身の順番がわからない
• レコードをオブジェクトと捉えたときに自身の順番はオブジェクトの属性ではない
• 1通りの順序しか保存できない

方法5 レコードの順番を持つテーブルを作る

ここから方法7までは2つ以上のテーブルを使う方法です。
方法1～4の例で示したテーブルの名前が、動物テーブルだったとします。動物には名前や系統などの属性がありますが、方法1～4に出てきた順番や優先度は、動物の属性とは言えません。それが同じレコード内にあることが許せない感情になる人がいるかもしれません。それを言うとDBでよく使うidやcreated_atカラムも動物の属性ではないのですが、順番というのは、システムの重要なロジックには関係なく、ある一画面で表示するためだけに付けることが多く、将来的に使わなくなったり、複数画面で異なる順番が必要になったりすることがあるものです。
そのため、将来を見越すと別テーブルに分けておいた方が無難です。

animalテーブル

id	name
#1	Cat
#2	Dog
#3	Rat

animal_orderテーブル

id	animal_id	pos
#1	animal1	2
#2	animal2	1
#3	animal3	3

方法1のanimalテーブルからからposカラムを分離しただけですが、これにより、順序の更新でanimalテーブルを触ることが無くなりました。
現実世界だと名簿を用いた方法と言えそうです。先生が生徒の順番を書いた名簿を持っています。

さらに、次のようにすることで利用するユーザーごとに異なる順番を保持できるようになります。

animal_orderテーブル

id	user_id	animal_id	pos
#1	user1	animal1	2
#2	user1	animal2	1
#3	user1	animal3	3
#4	user2	animal1	1
#5	user2	animal2	2
#6	user2	animal3	3

もちろんユーザーごとだけでなく、画面ごとに分けたり、期間ごとに分けたりもできるようになります。

実装の難易度　★★★　普通
KVSと相性　悪い

メリット

• 並び替えできるレコード数に上限が無い
• テーブルすべてを参照しなくても、あるレコードの自身の順番がわかる
• 複数通りの順序を保存できる
• レコードをオブジェクトと捉えたときに不自然なレコードが無い
• ドラッグ＆ドロップの並べ替えに適している

デメリット

• 複数テーブル必要になる
• 順序の入れ替えやレコードの追加ときに多数のレコードを更新する必要がある

この方法は、順序を復元するのに2つのテーブルから複数のデータを取得するのでKVSと相性が悪いです。RDBでしか使うべきではありません。
デメリットのうち、多数レコードの更新デメリットは、方法2～4と組み合わせることで解消できます。

方法6 レコードの順序を配列として保存する

これまでの方法には、「並び替えできるレコード数に上限が無い」という当たり前すぎるメリットがありました。もちろんこれまでの方法でも1つのテーブルに追加できるレコード数にデータベース仕様の上限がありますが、この上限は十分に大きい数として無視していました。この上限無しのメリットを捨てると、次のような方法が考えられます。

animalテーブル

id	name
#1	Cat
#2	Dog
#3	Rat

animal_orderテーブル

id	animal_order
#1	animal2, animal1, animal3

animal_orderにanimalテーブルのidを配列で保存しています。
何万件というテーブルの配列を一つのデータとして保存するのは現実的で無く、idの形式によってはすぐに文字数制限に達してしまう可能性があるため、レコード数の上限ありとなります。

現実世界でいうと写真を用いた方法といえそうです。並びを写真に残しておき、あとでそれを見ながら順番を再現します。

実装の難易度　★★　易しい
KVSと相性　良い

メリット

• テーブルすべてを参照しなくても、あるレコードの自身の順番がわかる
• 複数通りの順序を保存できる
• レコードをオブジェクトと捉えたときに不自然なレコードが無い
• ドラッグ＆ドロップの並べ替えに適している
• 順序の入れ替えやレコードの追加ときに多数のレコードを更新する必要が無い

デメリット

• 並び替えできるレコード数に上限がある
• 複数テーブル必要になる

上限無しを捨てるだけで多くのメリットが得られるのが分かると思います。
実は、上限が問題になることはほとんどありません。なぜなら、手動で順番を変えるという機能が要求される場面は、操作者がレコードをすべて把握できるような少ないデータ数を扱うときが多いからです。100個を超えてくると手動並び替えることよりも、自動で並び替えたり検索して探したり、あるいはお気に入り機能のように一部のレコードだけ並び替えるということが多くなります。

また、テーブルが2つになりますが順序テーブルは一つのレコードしか使っていませんのでKVSと相性が良いです。3番目のレコードだけを取り出したいといったときも、データベースを検索する必要はありません。

この方法を使う場合は、idの形式と文字数制限を考慮して、ユーザーが並び替えできるレコード数の上限を必ず設けなければなりません。

方法7 レコードの順番変更履歴を持つテーブルを作る

方法7と方法8では、初出ではないと思うのですが、私が考えた方法を紹介します。
まずメリットとデメリットを見てみます。

実装の難易度　★★★★　難しい
KVSと相性　悪い

メリット

• 並び替えできるレコード数に上限が無い
• 複数通りの順序を保存できる
• レコードをオブジェクトと捉えたときに不自然なレコードが無い
• ドラッグ＆ドロップの並べ替えに適している
• 順序の入れ替えやレコードの追加ときに多数のレコードを更新する必要が無い

デメリット

• 複数テーブル必要になる
• テーブルすべてを参照しないと、あるレコードの自身の順番がわからない

この方法は、メリットが多いだけでなく、なんと、過去のある日時にどんな順序だったのかを再現することができます。
その代わり、実装が難しいです。順序を復元するのに変更履歴を辿っていくのでKVSに向いていません。
テーブルは次のようになります。

animalテーブル

id	name
#1	Cat
#2	Dog
#3	Rat

animal_update_orderテーブル

id	animal_id	pos	created_at
#1	animal1	1	0:01
#2	animal2	2	0:02
#3	animal3	3	0:03
#4	animal2	1	0:11
#5	animal3	2	0:12

created_atは日時ですが、説明のために日を省いています。
animal_update_orderテーブルはどのようなテーブルかというと、ある時間にあるデータが何番目に移動したかを保存しています。例えば、#5は0:12にanimal3が2番目に移動したことを意味します。このテーブルから次の手順で順序を復元します。

1. まず、animal_update_orderテーブルをanimal_idでグループ化して、最新のレコードだけのテーブルにします。

id	animal_id	pos	created_at
#1	animal1	1	0:01
#4	animal2	1	0:11
#5	animal3	2	0:12

2. animalテーブルと同じ要素数の配列の枠を用意します。

1	2	3

3. 新しいレコードから順に見ていきます。レコード#5はanimal3を2番目に置きます。

1	2	3
	animal3

4. レコード#4はanimal2を1番目に置きます。

1	2	3
animal2	animal3

5.レコード#1はanimal1を1番目に置こうとしますが、既に1番目は埋まっています。次に2番目に置こうとしますが、2番目も埋まっています。よって3番目に置きます。

1	2	3
animal2	animal3	animal1

これで順序を再現できました。

この方法には注意点があって、並べ替えを行うときは、下位のレコードを上位に差し込むということしかできません。例えば、間違って1番目にあるanimal2を普通に3番目に持ってきてしまうと、こうなります。

id	animal_id	pos	created_at
#1	animal1	1	0:01
#2	animal2	2	0:02
#3	animal3	3	0:03
#4	animal2	1	0:11
#5	animal3	2	0:12
#6	animal2	3	0:13

順序を再現するとこうなってしまいます。

1	2	3
animal1	animal3	animal2

animal2を3番目に持ってきただけなのに、animal1とanimal3が逆転しました。これを防ぐには、animal2を3番目に持ってくるにはanimal2は動かさず、animal1とanimal3を上位に移動します。

id	animal_id	pos	created_at
#1	animal1	1	0:01
#2	animal2	2	0:02
#3	animal3	3	0:03
#4	animal2	1	0:11
#5	animal3	2	0:12
#6	animal3	1	0:13
#7	animal1	2	0:13

この実装は少し頭を使いますね。

実は履歴テーブルの操作を#1から順に再現することで、上位のレコードを下位に差し込むということもできるようになりますが、履歴テーブルをすべて参照しなくてはなりませんし、計算時間もかかります。

順序の更新履歴だけで言えば、方法5と方法6でタイムスタンプを押せば実装可能です。しかし、その場合、更新履歴テーブルが膨れ上がります。更新履歴を最小容量で保存できるのが方法7です。

方法8 レコードに順番変更情報を持たせる

さて、方法7で更新履歴が不要なら次のようにposとpos_updated_atを使って、一つのテーブルで完結できます。もちろん方法5と組み合わせてテーブルを分けても大丈夫です。

id	name	pos	pos_updated_at
#1	Cat	1	0:01
#2	Dog	1	0:11
#3	Rat	2	0:12

方法7と同じように順序を復元できます。

実装の難易度　★★★★　難しい
KVSと相性　悪い

メリット

• 並び替えできるレコード数に上限が無い
• 1つのテーブルで完結する
• 複数通りの順序を保存できる
• ドラッグ＆ドロップの並べ替えに適している
• 順序の入れ替えやレコードの追加ときに多数のレコードを更新する必要が無い△

デメリット

• テーブルすべてを参照しないと、あるレコードの自身の順番がわからない
• レコードをオブジェクトと捉えたときに自身の順番はオブジェクトの属性ではない

個人的には、方法3方法4を使うくらいならこちらを採用したいです。

おわりに

色々な方法がありますので、シーンに合わせて使い分けたいです。

並び替えできるデータを保存しないといけない場面は、特定のクライアント向けだったり、マイリスト機能のようにレコード数が少ない場面が多く、実装しやすい方法2と方法6が良さそうです。

idの配列をデータに保存するという方法6は抵抗がある方も多いと思います。私もそうだったので方法7方法8を考えたのですが、デメリットはその抵抗感くらいですので、コッド先生には怒られるかもしれませんが積極的に使っていこうと思います。

とはいえ、開発チーム内での共有や後から開発に携わる人のこと考えて、無難な方法1に落ち着くことが多いですね。