【図解】パスルーターのアルゴリズムを理解する：Express / Hono / Gin / Fiber
APIを書いていると、何気なくこれを書きます。
app.get("/users/:id", handler)
でも内部では、毎回こんな問題を解いています。
GET /users/123は、登録済みルートのどれに当たるのか？
この記事では、Express / Hono / Gin / Fiber などのパスルーターを、細かい実装差ではなく「どう探しているか」で理解します。
※ 学習用に単純化しています。実際の実装は、バージョンやオプションによって細部が変わります。
まず結論
パスルーターの仕事は、だいたいこの2つです。
| 役割 | やること |
|---|---|
| 探す |
GET /users/123 に合うルートを見つける |
| 抜く |
:id などの値を params に入れる |
同じURLでも「探し方」が違う
ざっくり対応させると、こうです。
| 方式 | 代表例 | イメージ |
|---|---|---|
| Linear Scan + RegExp | Express型 | 上から順番に試す |
| Trie | Hono TrieRouter | 区切りごとに木をたどる |
| Radix Tree | Gin / httprouter | 共通部分を圧縮した木 |
| Big RegExp | Hono RegExpRouter | 1回の正規表現マッチで決める |
| treeStack | Fiber | 共通prefixで候補を減らす |
ルート登録は「地図を作る時間」
リクエストが来る前に、ルーターはルートを内部構造へ保存します。
パスは、だいたいこんな部品に分解されます。
/users/:id/posts に /users/123/posts が来たら、:id = 123 になります。
ルーターが見るのは「path」だけ
?tab=recent のようなクエリ文字列は、基本的にルート照合の対象ではありません。
ルーターはまず、/users/123/posts という「道順」だけを見ます。
1. Express型：上から順番に試す
Expressは、ルートパスを path-to-regexp でマッチ可能な形にし、登録されたルートを順番に評価するイメージです。
考え方はシンプルです。
ただし、順番が意味を持ちます。
そのため、Express型では静的なルートを先に置くと読みやすくなります。
app.get("/users/new", newUserHandler)
app.get("/users/:id", userDetailHandler)
2. Trie：パスを木としてたどる
Trieは「共通するprefixを共有する木」です。
/users/123/posts が来たら、こう進みます。
ポイントは、全ルートを上から全部見るのではなく、パスの形に沿って進むことです。
Honoの TrieRouter は、このTrie-treeの考え方に近いルーターです。
3. Radix Tree：Trieを圧縮する
Trieを1文字ずつ持つと、ノードが細かくなります。
Radix Treeは、共通部分をまとめて持ちます。
このように、/user/ という共通prefixを1本の枝にできます。
Ginは httprouter をベースにしており、内部ではRadix Tree、つまり圧縮Trieを使うルーターとして説明できます。
4. Hono RegExpRouter：大きな正規表現にまとめる
Honoの RegExpRouter は、各ルートを順番に正規表現で試すのではなく、ルートパターンを大きな正規表現にまとめる発想です。
イメージとしては、こうです。
ただし、すべてのルーティングパターンを RegExpRouter だけで扱えるわけではありません。
そこでHonoは、SmartRouter で使えるルーターを選びます。
5. Fiber：treeStackで候補を絞る
Fiberは、登録済みルートから事前にルート木を作り、HTTPメソッドや共通prefixを使って候補を減らします。
GET /api/users/123 が来たときのイメージです。
全部のルートを見るのではなく、「このprefixならこの箱」という形で探索範囲を小さくします。
paramsはどう取り出す？
パラメータ付きルートは、名前と値を対応させます。
: が付いた部分は「その位置の値を保存する」というマーカーです。
静的・動的・ワイルドカードの優先順位
同じ場所に、複数の候補があることがあります。
多くの木ベースルーターでは、考え方としてはこの順に探すと理解しやすいです。
Express型では、基本的に登録順の影響が強くなります。
木ベースでは、静的ルートと動的ルートの優先度を構造として扱いやすくなります。
速さの感覚
厳密なベンチマークは環境で変わります。ここでは、効きやすい要素だけ見ます。
| 方式 | 得意なこと | 気にすること |
|---|---|---|
| Linear Scan | 実装が素直、順番で制御しやすい | ルートが増えると比較が増えやすい |
| Trie | 全件走査を避けやすい | 木の構築と優先順位設計 |
| Radix Tree | Trieよりノードを圧縮しやすい | 実装が少し複雑 |
| Big RegExp | 1回の照合に寄せられる | 対応できるパターン、起動時のcompile |
| treeStack | 候補を先に絞り込める | prefix設計と残り候補の比較 |
ルーター設計で迷ったら、この見方をする
パスルーターを速くする一番のコツは、特殊なテクニックよりも、ルートを読みやすく整理することです。
/api/users/:id
/api/users/:id/posts
/api/posts/:id
このようにprefixが揃っていると、木ベースのルーターでも、人間の目でも追いやすくなります。
まとめ
この記事の要点です。
- Express型は、登録順にルートを試すイメージ
- Honoは、
RegExpRouter/TrieRouter/SmartRouterの組み合わせで高速化する - Ginは、
httprouterベースのRadix Treeで高速に探す - Fiberは、事前計算した
treeStackで候補を絞る -
:idは「その位置の値を名前付きで保存する」ためのマーカー
普段書いている app.get("/users/:id") の裏側では、ただの文字列比較ではなく、URLを素早く見つけるためのデータ構造が動いています。