IPルーティングテーブル検索を高速に行うためには，全頁で挙げたRadix treeの問題を解決する必要があります。Poptrieではそれらの問題を解決するために，以下の2つのアプローチを採用しています。

1. メモリアクセスを含む命令数の削減
2. CPUキャッシュの効率化

木構造を辿る操作の計算量は木の深さに比例します。Poptrieでは，多分木を拡張し木の深さを浅くすることで，命令数を削減しています。

CPUキャッシュを効率的に利用するには，一般に

1. データアクセスの局所性を上げる
2. メモリ使用量を削減する

という2つの方式があります。ルーティングテーブル検索は，データ構造を変更することで多少データアクセスの局所性を上げることはできるかもしれませんが，入力されるデータはパケットの宛先アドレスに依存するため，データアクセスの局所性を上げるのは困難です。Poptrieでは，メモリ使用量を削減し，L3キャッシュサイズ内に収まるサイズまで圧縮し，簡潔データ構造にすることでCPUキャッシュを効率的に利用しています。

下図はRadix treeを可視化したものです。経路のあるノードを赤色，経路のないノードを緑色，エッジを灰色で表現しています。経路数の多い/16，/24のプレフィックス長に赤色のノードが集中しているのがわかります。各ノードは最低2つのポインタと経路へのポインタを持つため，64ビットモードでは最低24バイト必要です。この図からも，ルーティングテーブルをRadix treeで表すと，ノード数，エッジ数ともに非常に多く，巨大な木構造であることがわかります。

一方，下図はPoptrieを可視化したものです。具体的なデータ構造とアルゴリズムは後述しますが，中心（ルート）の青色が高速化で導入するDirect Pointingの配列（Direct Pointingパラメータs=18のとき，1 MiB程度），黒色が中間ノード（internal node; 24 byte），緑色がリーフ（leaf; 2 byte）ノードです。この図からノード数が大きく削減できている様子がわかるかと思います。具体的な評価については後述しますが，ルートの1 MiB程度を加味しても1/10以下のメモリフットプリントに収まります。