非クラスター化インデックスでもソートは早くなりますか？

Question

プログラミング初心者です。
現在個人でシステムを作成しており、現在のデータは数百行しかありませんが、将来的には数千行、数万行になるかもしれないテーブルがあります。
##困っていること

様々な条件でソートをしたいのですが、使用しているデータベースのスペックが低いので、処理の速さと負荷の大きさが気になります。
※どのソートも一つの列に対してソートします
##環境
使用データベース
・SQL Server (Azure SQLServer)
・Azureサービスでメモリ容量など詳細を見ることはできないのですが、Freeプランを使用しています
・Azure Database
・容量 250GB ※将来増量予定

テーブル定義 ※将来的に数千~数万行を想定

ID nvarcahr(450) 主キー
Title nvarchar (450)
ViewCount int decimal(20, 0)    //ソートしたい列
LikeCount int decimal(20, 0)    //ソートしたい列
CommentCount int decimal(20, 0) //ソートしたい列

##疑問点・調べたこと

調べてみると、**インデックスを付けるとその列で『データが並んで保存される』**ので、ソートの処理が早くなる、といった旨の記事を読みました。

より調べてみると、インデックスには種類があり、ここで指しているインデックスは『クラスター化インデックス』なのではと思っております。

しかし、『クラスター化インデックス』は複数個付けることができず、今回は複数列に対してインデックスを付けたいので足りません

そこでもっと調べてみると、『非クラスター化インデックス』は複数付けることができることがわかりました。
しかし、この**『非クラスター化インデックス』は、『データを並び替えて保存しない』**ということで、今回のソートをする目的でつけても、処理が早くなる、負荷が減るといった風にはならないのではと心配しております

とても初歩的な質問かもしれないのですが、どうか教えて頂けないでしょうか。

Comments

[m.ts10806]

実際のテーブル定義を提示されたほうが良いですし、「データベースのスペックが低い」だけでは情報が何もないです。詳細追記してください。
あと、タグも追加してください。
https://teratail.com/tags/SQL+Server
https://teratail.com/tags/%E3%83%91%E3%83%95%E3%82%A9%E3%83%BC%E3%83%9E%E3%83%B3%E3%82%B9

[kare-]

申し訳ございません、テーブル定義とタグの追加をしようと思います。
ご指摘ありがとうございます。

Answer 1

図で確認したほうが理解しやすいと思うので、例示を出します。
例えば、質問本文のテーブルがクラスターインデックス付きでこのように保存されているとします。

厳密には違いますが、データベースのファイルには図の様にid順に保存されています。
行はexcelでいう行番号です。
クラスターインデックスの特徴は、あとからどのようなidの値のレコードをinsertしても、保存するデータはid順に並ぶのが特徴です。idが 10 -> 40 -> 30 -> 20 -> の順にレコードをinsertしても、保存するデータは図の様にid昇順に記録されます。

これに対して非クラスターインデックスはインデックス対象の列と行番号のペアをインデックス対象の列の昇順で本表とは別領域に記録します。イメージとしては以下の様になります。

データそのものを並び替えて保存するのではなく、インデックスの元となる値の順に行番号を保存しています。

例えばview_countが5000以上のレコードを抽出したい場合、本表で抽出するにはテーブル全体を走査しないといけませんが、非クラスターインデックスを参照するとview_countが5000の境界がすぐわかります。境界以降のデータで、行番号と同じデータをそのまま出力すれば良いわけです。行番号の探索時間はpkを探索する時間よりも短いです。

数百行程度のデータだと効果の実感が薄いですが、数万行、数百万行のデータになると顕著に効果が出てきます。
質問文の要件だと、非クラスターインデックスを view_count, like_count, comment_count それぞれで作成すると検索効率が格段に上昇すると思います。

おまけ：オーダ記法での探索コスト

非クラスターインデックスなしでview_countを条件に検索するコスト：Ο(n)
非クラスターインデックスありでview_countを条件に検索するコスト：Ο(log(n))
（内訳）
非クラスターインデックスで view_count = n や view_count > n を探索するコスト：Ο(log(n))
非クラスターインデックスでマッチしたレコードからデータ本体を取得するコスト：Ο(1)
n > log(n) なので、非クラスターインデックスありの方が格段に速くなります。
（例えばn = 100,000 であれば log(n) = 17 くらいです。6000倍くらい早くなる計算です）

Comments

[kare-]

ありがとうございます！
非クラスター化インデックスも、インデックス対象の列の順で保存されてるんですね。
それだとソートする際は非クラスター化インデックスの有無で格段に効率が変わりますね。

オーダ記法という概念？も初めて知りました！
独学で勉強しているので、正直こういった単語を知らず検索が中々むつかしい状況でしたので大変助かります。

6000倍のくだりも感動しました。
プログラミングって知識一つで劇的に効率が変わるのが面白いですね！

表まで作って下さり、初心者の私にもわかりやすく教えてくださりありがとうございます。