DEIM Forum 2023 2a-2-4

Adaptive Radix Tree の多次元索引への拡張鈴木駿也†

杉浦 健人†

石川 佳治†可鏡†

陸† 東海国立大学機構名古屋大学大学院情報学研究科 〒 464–8603 愛知県名古屋市千種区不老町
Email: {ssuzuki, lu}@db.is.i.nagoya-u.ac.jp, {sugiura, ishikawa}@i.nagoya-u.ac.jp
あらまし

多次元索引は地理情報を始めとする空間データへの索引付けや複数列キーでの類似検索などに利用されており，近年では機械学習を利用した索引構造も提案されその性能改善が図られている．多くのデータベースで用いられている B+ 木を Z 階数曲線を用いて多次元索引へと拡張した研究として universal B 木（UB 木）が存在するが，各ノードに割り当てられるキー範囲が空間的に適したものにならない．一方で，トライ木を元とした索引構造はキーを上位ビットから階層的に分割するため，Z 階数曲線を適用したときに四分木のような理想的な分割となる．そこで，本研究ではトライ木ベースの索引構造として有名な adaptive radix tree を多次元データへ拡張した universal adaptive radix

tree (UART) を提案する．UART はトライ木の挿入性能を活用するとともに，Z 階数曲線の性質を利用することで範囲検索にも最適化し，二次索引として利用可能な構成として実装した．実験において提案する UART の性能を UB 木やR∗ 木といった既存の多次元索引と比較し評価した結果，読み書き両方において優れた性能であることを確認した．
キーワード 索引構造，多次元索引，Z 階数曲線．
用上では範囲検索の性能が劣化しやすいという課題がある．

1 はじめに3660

多次元索引は地理情報アプリケーションにおける空間データ
39の索引付けや，二次索引による類似検索など，その利用は多岐
2にわたる．多次元索引として広く利用されている R∗ 木 [1] は

14

32

48

48

14
12

範囲検索や近傍検索に特化しているが，挿入時のノード分割計
算量が高く，逐次的な更新に弱いという課題がある．近年では

36

2

1 2

12 14

機械学習を利用した索引構造も提案されその性能改善が図られ

19 32

36 39

48 60

19
1

図 1: UB 木における空間分割の例ている [2, 3] が，これらも逐次的な更新を重視しておらず，読
み書き両方において安定した性能を持つ汎用的に使用可能な多次元索引は少ない．
多次元索引の中でも，多くのデータベースで用いられている B+ 木 [4] を多次元索引へ拡張した研究として universal B 木（UB 木） [5] が存在する．UB 木は多次元データを Z 階数曲線に基づき 1 次元の Z 値 [6] に変換し，B+ 木のキーとして使用
する．UB 木は多次元データを扱うがその構造は B+ 木のままであるため，書き込みに対する性質なども B+ 木のそれを受け一方で，主な索引構造の 1 つとしてトライ木が存在する．ト
ライ木はキーを数ビットずつ分割し，葉ノードへのパスとして保存する．トライ木は検索にキー全体の比較演算を使用しない
ため，キー長の長いデータの索引付けに特化している．近年提案された adaptive radix tree（ART） [7] は，トライ木のノードとパスの圧縮により CPU キャッシュの利用効率を最適化した構造である．ART はインメモリデータベース管理システムである HyPer [8] の索引構造として使用され，近年でも多くの研究

継ぎ，空間索引としては逐次的な更新に強いという特徴を持つ．

例が存在する．例えば，ART を空間結合の際に使用できるよう

しかし，UB 木は多次元値を Z 階数曲線により 1 次元化し管拡張した研究 [9] が存在するが，これは一般的な空間問合せや理するが，ノード分割も 1 次元値として行うため，全体の空間更新に対応しておらず，汎用的な多次元索引として最適化され分割は最適なものとならない．図 1 に UB 木の空間分割を示ていない．

す．図 1 左の UB 木の色付きノードの対象とする範囲を，図 1

そこで，本研究では ART を汎用的な多次元索引として最適化

右の対応する色で表す．このように UB 木の各ノードの空間分

した，universal adaptive radix tree（UART）を提案する．UART

割は定まっておらず，非連続な領域やバラつきが存在し，あるは UB 木同様，与えられた多次元値を Z 階数曲線によって 1 次

ノードを包含する最小矩形（バウンディングボックス）が過剰元に変換した Z 値を挿入キーとして利用する．ただし，UARTに広がってしまうことがある．例えば，最下段の {19, 32} を持は変換した Z 値を上位から 1 バイトずつ分割し，階層的に空間つノードのバウンディングボックスは図中の下半分以上の空間を分割する．例として，Z 値の上位 2 ビットを用いて空間を分を占めるものとなるが，ノード内には左下の空間に対応するレ

割したものを図 2 に示す 1 ．図に示す通り UART における空間

コードは存在しないため無駄な領域を多く含む．このような無駄な領域の存在により索引層での枝刈りなども困難となり，実1：分割の単位は 1 バイトであるが，概念を直感的に説明するためにここでは 2
ビットのみの例を示す．

Node4
60

002

002
1, 2

102

012
19
112

002

12, 1432

112
48, 60
012

39

32

36

key

key

15
0 1 2
0 2 3 … 255

0 1 2 30 1 2 30 2 3 255

child pointer
0 1 2

15

…

48

a

14
12
2

36, 39Node16child pointer

191

図 2: UART における空間分割の例

b

c

d

a

Node48
key

255
0 1 2
… 47
1 0

child pointer

47

0 1 2

a

c

c

d

Node256
0child pointer
1

2

…
b

b

3

255

4

…
d

a

b

c

d

図 3: ART の中間ノード

分割は四分木のような理想的なものとなり，各ノードの対応するキーの範囲がそのバウンディングボックスと一致する．この性質を利用することで，UART では範囲検索時に索引層での積ノードが検索範囲と交差するか判定する場合には逐次的に次の極的な枝刈りや検索範囲への包含判定の効率化が行える．更に，範囲内の値を計算し，ノード範囲と比較する必要がある．次のART の構造を利用しノードサイズや木の深さを適応的に変化さ範囲内値の再検索時，根ノードから検索し直す方が簡単な場合

せることで，メモリ利用効率や検索効率を向上させる．また，でも，親ノードへの回帰を繰り返すような処理が発生しうる．

葉ノードには単一キーに対して複数の値を保存可能な構造を採

また，親ノードへの回帰毎に，そのノードが残りの検索範囲と用し，二次索引としても利用可能なよう実装する．

重複しているか判定する必要がある．

2 準

2. 2 Adaptive Radix Tree備

ART [7] はトライ木の中間ノードとパスを動的に変化させ，本章では，UART のベースとなる索引構造である UB 木とキー分布に最適化したものである．本節ではトライ木と，ART

ART について説明する．

のトライ木からの変更点である中間ノードとパス圧縮，そして

2. 1 Universal B 木

問合せ処理を説明する．

UB 木は多次元データを Z 階数曲線により Z 値に変換し，B+ 木に適用したものである．UB 木の問合せ処理は基本的に2. 2. 1 ト ラ イ 木
トライ木は葉ノードまでのパスにキー，葉ノードにレコード

B+ 木と同一であるが，範囲検索処理が大きく異なる．本節でを保存する木構造である．トライ木はパスに部分キーを保存す

は Z 値と UB 木の範囲検索処理を説明する．

える．そのため，各中間ノードは 2𝑠 個の子ノードのポインタを

2. 1. 1 Z 値
Z 値は，多次元データをその空間を充填する Z 階数曲線の上の開始点からの距離に変換した値である [6]．例えば，元々(0, 1) の点は，Z 階数曲線上でその開始点から 1 番目の座標にあるため 1 という値に変換される．多次元値から Z 値への変換
は，各座標値のビットを交互に配置することで計算できる．2
次元データの場合，x 座標値のビット列をx = 𝑥 𝑛 ...𝑥 2 𝑥1 𝑥0

るが，これはキーのデータ列を 𝑠 ビットずつ分割した値だと言持つ．トライ木の中間ノードは，子の数が 1 つの場合でも 2𝑠 個のポインタを持つ必要があるため，その多くがヌルポインタとなりうる [7]．

2. 2. 2 中間ノード
ART の中間ノードは子ノードの数によって種類を変更する．
ART はキーの分割ビット数が 8 であり，中間ノードは最大 256 個の子ノードのポインタを持つ．図 3 に ART の中間ノードを示
す．ART には Node4，Node16，Node48，Node256 の 4 種類の中間ノードがあり，それぞれの名前が最大の子の数を表す．

y 座標値のビット列を

Node4，Node16 はキー，ポインタをそれぞれ 4 個，16 個ず
y = 𝑦𝑛 ...𝑦2 𝑦1 𝑦0と表すとき，その Z 値のビット列はz = 𝑦𝑛 𝑥 𝑛 ...𝑦2 𝑥2 𝑦1 𝑥1 𝑦0 𝑥0

つ持つ．Node4，Node16 は 𝑖 番目のキーに対応する子ノードのポインタを，その 𝑖 番目として持つ．例えば，図 3 の Node4 は部分キー 0, 2, 3, 255 のみ保持し，その要素番号 3 となる 255 には部分木 𝑑 が対応する．

Node48 はキーを 256 個，ポインタを 48 個持つ．Node48 は部と表すことができる．同様に，各座標値を順番にはさみ合わせ

分キー 𝑖 に対応する子ノードのポインタを，要素番号 𝑖 のキーにることで任意次元のデータを Z 値に変換できる．

格納されている要素番号のポインタに持つ．図 3 の Node48 で

2. 1. 2 範 囲 検 索

は，部分キー 255 に対応する部分木 𝑑 の要素番号 47 を，キー配

UB 木の範囲検索は，範囲外の値を発見したときに次の範囲内

列の要素番号 255 に持つ．ART は分割ビット数が 8 であるため，の値を計算し，ジャンプすることで範囲外の走査を避ける [10]．

部分キーの値は 0 以上 255 以下となる．したがって，Node48

UB 木はノード分割が事前に定まっていないことやノードの空では探索を必要とせずにキー要素へ直接アクセスできる．

間分割に非連続な領域があることから，効率的な範囲検索が難Node256 は 256 個のポインタのみ持つ．Node256 はキー 𝑖 にしい．各ノードが Z 値の最大値と最小値しか持っていないため，対応する子ノードのポインタを，その 𝑖 番目に持つ．図 3 のArtNode A
A
ArtNode B
C

N

A

N

R

R
D

C
ART層

ArtNode C

T

AND

ANT

ART

CAT

UBNode A
UBNode B
D:𝑣1 T:𝑣2𝑣7

図 4: Adaptive radix tree

UBNode C:𝑣1 , 𝑣3 , 𝑣5

T

UBNode E
AT:𝑣1 , 𝑣3

UB層

UBNode D:𝑣7 , 𝑣8 , 𝑣9

図 5: Universal adaptive radix tree

Node256 では部分キー 255 に対応する部分木 𝑑 を，要素番号255 のポインタに持つ．Node256 も Node48 と同様に，キーの探索を必要としない．Node256 は元々のトライ木の中間ノード

重複を許した二次索引としての実装や，空間問合せおよび解析と同じ構造である．

処理におけるフィルタリング処理のための範囲検索性能を重視

2. 2. 3 パ ス 圧 縮する．

ART は子の数が 2 以上の中間ノードのみ作成し，パスを圧縮

図 5 に UART の概観を示す．なお，図 5 はキーを文字列としする．図 4 に ART の概観を示す．図 4 では，木全体で “C” かて表現している．ART 層はキーのプレフィックスを分割して保ら始まるキーは “CAT” のみである．そのため，根ノードから存することで空間を分割し，UB 層でデータを効率的に保持すのパス “C” には直接葉ノードのポインタを持ち，パス “AT” はる．ART 層は ART の中間ノードを拡張した ART ノードからな省略される．同様に，各中間ノードにおいて子ノードが 1 つしり，UB 層は UB 木の葉ノードを拡張した UB ノードからなる．

かないノードを省略することで，空間効率や検索効率を最適化

UB 層の UB ノードは二次索引として単一のキーに複数のレコー

する．省略されたパスは，続くノードのヘッダに保存する．

ドを保存可能にし，単一のキーへの値が集中した場合，ノードを分割して UB 木に置き換えられる．図 5 では UBNode A に

2. 3 問合せ処理
検索は，根ノードから葉ノードに到達するまで，与えられたキーの部分キー 𝑖 を用いてノード遷移して行う．Node4，Node16
では，ノード中のキー配列から 𝑖 と一致する値を持つ要素を探索し，その要素番号の子ノードへ遷移する．Node48 ではキー配列

キー “AND”，“ANT” とそれぞれに対応するレコード {𝑣1 , 𝑣2 } を保存している．また，UBNode B，C，D はキー “ART” にレコー
ド {𝑣1 , 𝑣3 , 𝑣5 , 𝑣7 , 𝑣8 , 𝑣9 } を保存する UB 木となっている．

3. 1 ART

層の 𝑖 番目に入っている要素番号の子ノードへ遷移する．Node256

ART 層は，キーとして与えられた Z 値を上位バイトから分

では 𝑖 番目の子ノードへ遷移する．各ノードで，部分キーが見割することで，多次元空間を階層的に分割する索引層である．

つからない場合や子ノードのポインタがヌルポインタである場

1 階層は 1 バイト（256 区画）単位で空間がグリッドに分割さ合，そこで検索を打ち切る．また，遷移先のノードに圧縮パス

れ，トライ木の性質により各グリッドへの効率的なアクセスがが格納されている場合，一致する限り部分キーを次に進める．

可能となる．以下では，ART 層における空間分割とノードレイ

圧縮パス全てが後続の部分キーと一致しない場合は検索を打ち

アウトについて詳細を述べる．

切る．

3. 1. 1 空 間 分 割

挿入は，検索の手順でノード遷移して行う．遷移先がなくなっ

UART は，図 2 で示したように，Z 値のキーを分割することた時，後続の部分キーをキーとして，レコードを持つ葉ノード

でデータの空間分割を理想的なものとする．図 2 は次元数を 2，

をそのノードに挿入する．遷移先のノードの圧縮パスが続く部

分割ビット数を 2 とした場合の UART の空間分割であり，図左

分キーと一致しなければ，新たな中間ノードを作成し，現在のの色付きノードが分割する領域を図右の対応する色の領域としノードと葉ノードを挿入する．挿入時にノードの持つ子の数がて表している．図 2 で示したように次元数，分割ビット数がと許容量の上限に達している場合は，ノードを 1 段階大きいもの

もに 2 の場合，根ノードから深さ 1 のノードは四分木と同じ空に拡張して挿入する．

間分割となり，同様に中間ノードの子ノードは親ノードの空間

削除は挿入処理と同様である．該当する葉ノードをその親を 4 つのグリッドに分割していく．

ノードから削除し，要素数が閾値を下回れば一段階小さいノー

実際には，UART の分割ビット数は 8（1 バイト）であるた

ドに縮小する．子の数が 1 つになる場合，子ノードと親ノード

め，各階層で 256 個のグリッドに分割する．2. 1. 1 項で説明しの入れ替えを行い，パスを圧縮する．

たように，Z 値は多次元データの各次元のビットを交互に配置している．各次元の最上位ビットは，その次元の全ドメインに

3 Universal Adaptive Radix TreeUART は ART 層と UB 層からなり，キーとして Z 値を使用
して多次元索引に拡張したものである．特に，本稿では UARTの空間索引や OLAP での利用を念頭に置く．そのため，キーのおいて上位半分以上であるかを示し，続くビットはそれぞれのドメインにおいて同様である．したがって，Z 値の上位 𝑠 ビット（プレフィックス）は空間の全ドメインにおいて，2𝑠 個のグ
リッドのどれに属するかを示す．同様に，後続の 𝑠 ′ ビット（サ′フィックス）はそのグリッド内において 2𝑠 個のサブグリッド

𝑦

3

4

1

2

header
ArtNode node level child deleted compressed tmp
Node4 ~
flag type
count count
path
UBNodeNode256
1 bit 2 bit 1byte 1 byte 1 byte
8 byte8 byte
図 7: ART ノード𝑥

図 6: UART の分割範囲と検索範囲の例

Node4，Node16，Node48，Node256 の 4 種類があるが，それぞれ共通のヘッダを持つ．ArtNode ﬂag は ART ノードと UB ノーのどれに属するかを示す．UART においてはトライ木による検ドの識別，node type は ART ノードの Node4 から Node256 の索性能を活用するために，ビット数として 8 を使用し，対象空識別に用いる．level は現在のノードの共通プレフィックスの長間を階層的に分割する．

さである．child count にはノードの持つ子の数，deleted count

UART ではこの階層的な空間分割を範囲検索の効率化に利にはノードから削除された子の数を保存する．compressed path

用する．上述したように，あるグリッドに含まれるサブグリッには圧縮されたパスを保存する．compressed path は 8 バイトでドはそのグリッドに完全に包含される．つまり ART 層においあるが，圧縮したパス長に 1 バイト使用するため，1 つのノーて，上位のノードで行った検索範囲との交差判定の結果は，下ドで最大 7 バイトのパスを圧縮する．UART ではパス中に完全位ノードでの交差判定の効率化に利用できる．図 6 に，UARTにキーを保存する必要があるため，圧縮できるパスが 7 バイトの空間分割と検索範囲の例を示す．検索範囲は赤と青の辺から以上の場合，複数ノードにわたってパスを圧縮する．

なる矩形であり，赤色の辺が始点側，青色の辺が終点側を示す．

また，UART では対象の ART ノードまでのプレフィックス

空間 1 は，x 軸および y 軸ともに始点・終点の内側にあるため，のみに対応するレコードを保持するためのノードとして，一空間 1 を持つノードは検索範囲に完全に包含される．したがっ

時保存用の UB ノード（tmp UBNode）を各 ART ノードに用意て，空間 1 以下のノードにおいて追加の包含判定は不要であり，する．つまり，ART ノード内の各レコードがそれぞれ 1 バイ

全てを検索対象としてフルスキャンできる．一方，空間 3 は x

トのキーに対応した子ノードを持つのに対し，tmp UBNode は軸に関して検索範囲に包含されているが，y 軸において終点側

NULL キーに対応する UB ノードである．UART では前述したと交差している．そのため空間 3 以下のノードでは，y 軸の終ように各階層 1 バイトを用いて空間を 256 分割するが，ある点側のみで包含しているかを確認すればよい．同様に空間 2 でキーに偏りが発生している際に不用意に空間分割してしまうと，は x 軸の終点側，空間 4 では x 軸および y 軸で終点側と比較す

分割した子ノードのほとんどにレコードが含まれない可能性がることで包含判定を効率化できる．

ある．特に，UART はトライ木を基にした非平衡木であり，そまた，下位ノードでの包含判定において，上位層におけるのような疎な空間分割を繰り返すことで木全体のバランスが大キーの情報が不要である点も利点となる．UART では上述した

きく崩れてしまう可能性がある．そのため，キーに対応するレように上位ノードで包含されなかった次元のみを確認すればよ

コードが少数しか存在しないものを一時的にヘッダで保持するいが，各次元の値が包含されないのは上位ノードのキーのプレことで，キーに偏りがある際の平衡の崩れを抑えている．

フィックスが始点側ないし終点側のキーのプレフィックスと一致したときのみである．つまり，下位ノードでは自身の階層に

3. 2 UB

層

対応するサフィックスのみを用いて包含判定を行えばよい．こUB 層は UB ノードと UB 木からなる．UB ノードは，保存すのように，階層的な空間分割を持たない UB 木では各次元でのるキーの共通プレフィックスをパスとし，キーのサフィックス

包含判定にキーの全バイトが必要であるのに対し，UART ではとレコードの配列のペアを複数持つ．図 5 の leaf A は，共通プ階層構造を利用することで効率的な包含判定が可能となる．

レフィックスが “AN” であり，“D” と “T” のサフィックスを持ART ノードが Node48 または Node256 である場合，現在の値から次の検索範囲内の値（NextJumpIn 点）を計算し [11]，範

つ．したがって UBNode A はキー “AND”，値 𝑣1 のレコードとキー “ANT”，値 𝑣2 のレコードを持つ．

囲検索での子ノードの走査を効率化する．UART は空間のグ

UB ノードは UB 木の葉ノードを二次索引に対応させたもの

リッド分割とプレフィックスの共有により，各階層 1 バイトでである．図 8 に UB ノードのレイアウトを示す．UB ノードは

NextJumpIn 点を計算できる．更に，トライ木では 1 バイトで表

ヘッダとレコード領域，メタデータ配列から構成される．

されるキーへ 𝑂 (1) でアクセスできるため，NextJumpIn 点の計算およびその遷移先へのアクセス共に効率よく行える．

ヘッダの ArtNode ﬂag は ART ノードと同様，ART ノードとUB ノードの識別に用いる．preﬁx length は UB ノードの共通

3. 1. 2 ART ノード

プレフィックスの長さである．block size にはレコード領域の大ART ノードは ART の中間ノードと概ね同様の構造である．

きさ，deleted size はレコード領域中の削除された領域の大き

図 7 に ART ノードのレイアウトを示す．

ART ノードは ART の中間ノード同様，2. 2. 2 項に示したさを保存する．metadata array は対応するレコードへのアクセスに用いるメタデータの配列である．meta count には保持してheader

metadata arrayrecord region

meta metadata data

suffix record suffix record record
posting list

ArtNode A
ArtNode BNposting list

ArtNode UB-inner prefix meta block deleted next
flag
flag
length count size size node
1 bit
1 bit
14 bit 1 byte 1byte 1 byte 8 byte
図 8: UB ノード

A

C

R

UBNode A
UBNode B
D:𝑣1 T:𝑣2
𝑣7

T

UBNode C:𝑣1 , 𝑣3 , 𝑣5

UBNode D:𝑣7 , 𝑣8 , 𝑣9

図 9: 部分木の存在するキー（“CUP”）を挿入した状態

ArtNode A
ArtNode B

間ノードの識別フラグと，兄弟ノードのポインタである．

A

N

レコード領域中には，キーのサフィックスと対応する複数のレコードである転置索引（図中 posting list）を持つ．転置索引には単一のサフィックスに複数のレコードを保存可能であり，二次索引として利用できる．転置索引中，レコードはその値で整列する．
メタデータ配列はレコード領域中の転置索引を参照するため

U

UBNode E’
UBNode E’’
T:𝑣1 , 𝑣3
P:𝑣1“”

いるメタデータの数を保存する．UB-inner ﬂag と next node は

UB ノードが UB 木へ置き換わった際に使用する UB 木内の中A

ArtNode CCR

ArtNode C

UBNode A
UBNode B
D:𝑣1 T:𝑣2
𝑣7

UBNode C:𝑣1 , 𝑣3 , 𝑣5

UBNode F
BIG:𝑣1T

UBNode E
AT:𝑣1 , 𝑣3

UBNode D:𝑣7 , 𝑣8 , 𝑣9

図 10: 部分木の存在しないキー（“BIG”）を挿入した状態のメタデータの配列である．各メタデータはその参照するレ
コードのサフィックスで整列している．同一のサフィックスを持つ転置索引が存在する場合，それらを指すメタデータは参照
する最大のレコードで整列する．

置き換える．
共通プレフィックスを持つ UB ノードが存在していない場合，

ART ノードのヘッダ中の UB ノードに挿入する．つまり，ART
ノードからキー長 0 の部分キーで，そのノードと同じ共通プ

3. 3 問合せ処理

レフィックスを持つ UB ノードに挿入する．図 10 に，図 5 にUART は挿入と削除，範囲検索をサポートする．キーは多次元座標で与えられ，Z 値に変換して処理する．

3. 3. 1 更新キー “BIG”，レコード 𝑣1 を挿入した状態を示す．図 5 には “B”
から始まるキーが存在しないため，ArtNode A からパス “B” は存在しない．そのため，図 10 では UBNode F を新たに作成し，本項では，挿入および削除の問合せ処理を説明する．説明のArtNode A のヘッダ（部分キー “” のパス）に挿入する．ヘッダ

簡略化のためキーを文字列として表現しているが，実際は Z 値

中の UB ノードに空き領域がなくなった場合，UB ノードを分で同様の処理を行う．

割し，ART ノードの子ノードとして挿入する．上述の分割と同挿入は，2. 3 節の検索処理と同様の手順で対象となるキーを様に，最大で現段階の ART ノードの残りの子ノード数だけ新検索し，到達したノードにレコードもしくは新たな UB ノード

たに作成することで，段階的に ART ノードおよび空間の分割を挿入する．挿入処理は主に対象キーとの共通のプレフィック

数を拡大する．

スを持つ UB ノードが存在するかどうかで処理が異なる．

UB ノードの検索中，ART ノード中の圧縮パスと対象キーの共通プレフィックスを持つ UB ノードが存在している場合，

サフィックスが一致しない場合は，一致しなかったサフィック到達した UB ノードに対象のキーのサフィックスとレコードをスでの分岐を表す ART ノード生成する．つまり，検索キーと挿入する．UB ノードに空きがない場合，レコードを複数の新圧縮パスとで一致する部分を自身の圧縮パスとして持つ新たなたな UB ノードに分割する．分割時，分割後の UB ノードを持ART ノードを生成し，元々の ART ノードを子ノードとして挿つ新たな ART ノードを作成し，分割前の UB ノードが存在した

入する．その後，挿入対象のレコードについてはヘッダ中の UB

パスに挿入する．図 9 に，図 5 にキー “CUP”，レコード 𝑣1 を挿ノードへサフィックスを用いて挿入する．図 11 に圧縮パスとサ入した状態を示す．図 9 では，図 5 の UBNode E が UBNode E ′と UBNode E ′′ に分割している．新たに生成した ArtNode D に

UBNode E ′ と UBNode E ′′ を挿入し，ArtNode D は ArtNode A

フィックスの不一致時の例を示す．元々の ART ノードは圧縮パ
ス “AAAAA” を持つが，挿入キーのサフィックスは “ABCDE. . . ”
であり，一致しない．このとき，共通する部分キー “A” を持つに挿入する．なお，キーのサフィックスが更に共通のプレフィッ

新たな ART ノードを作成し，元々のノードの圧縮パスを縮小

クスを持つ場合，新たな ART ノードの圧縮パスとして保存す

して挿入する．新たな ART ノードは挿入キーとプレフィックス

る．また，UB ノードはレコード数の多い順に最大で 4 つ作成が一致するため，そのヘッダに UB ノードを作成して挿入する．

し，残ったレコードは新たな ART ノードのヘッダ中の UB ノー

削除は挿入処理と同様に，2. 3 節の検索処理で UB ノードをドに保存する．UB ノードの分割時，キーを 1 つしか持たない

検索し，対象レコードを削除する．UB ノード内のレコードが全場合はその UB ノードをレコード内の値をキーとする UB 木に…

…

inserting suffix“ABCDE…”compressed pathcompressed path “” suffix“AAAAA”“A”“BCDE…”“A”…

compressed path“AAA”

表 1: 実験用サーバの構成

CPUIntel(R) Xeon(R) Gold 6258R (two sockets)

RAM

DIMM DDR4 (Registered) 2933 MHz (16GB × 12)

OS

Ubuntu 20.04.5 LTS

Compiler GNU C++ ver. 9.4.0…
てそのスループットを測定する．表 1 に本実験で使用する環境

図 11: 圧縮パスの縮小と新規ノードの挿入を示す．
評価実験の比較対象として，UB 木と R∗ 木を用いる．UB 木
60

002

002
1, 2

102

012
19
112

002

12, 1432

112
48, 60
012

39

32

36

化した B+ 木である．UB 木は C++を用い，二次索引として実48装したものを用いる．R∗ 木は挿入アルゴリズムにより各ノー

14
12
2

36, 39は 2. 1 節で紹介したように，キーとして Z 値を使用して多次元

191

図 12: UART の範囲検索

ドの対応空間を最適化し，範囲検索に特化した R 木 [12] である．R∗ 木は C++での boost2 と libspatialindex3 の実装を用いる．

boost の実装は高速であるが 4 次元以上に対応していないため，高次元での性能特性のために libspatialindex の実装を用いる．

て削除された場合，そのノードを親ノードから削除する．ART

データセットとして，各次元の値が Zipf の法則に従うようノードの持つ子ノードが少なくなった場合，1 段階小さい ART

多次元値を生成したシミュレーションデータ（Zipf）と，アメノードに縮退する．検索に失敗した場合は処理を打ち切る．

リカの地形データ中のポイントオブジェクトを表す実データ

3. 3. 2 範 囲 検 索
範囲検索は，深さ優先探索によって検索範囲と重複する範囲（USA）を用いる．Zipf データセットは各次元独立に近似的に
式 (1) に示す Zipf 分布に従う 4 ．

を持つノードを探索する．入力として検索範囲の始点および終𝑓 (𝑘; 𝛼, |𝑊 |) = ∑点の座標が与えられ，それらを Z 値に変換して以下のように処理する．
最初に，範囲内最小のキーを持つ UB ノードを，2. 3 節の検索処理と同様に検索する．最小キーの検索処理に失敗した場合，そのキーより次に大きい範囲内のキーを持つ UB ノードに遷移する．UB ノードではノード中のレコードを走査し，範囲内のキーを持つレコードのみ返す．UB ノードの走査終了後，その親の ART ノードから次に検索範囲と重複する UB ノードに遷移する．ART ノードの走査終了後，同様にその親ノードから次に検索範囲と重複する子ノードに遷移する．ART ノードのヘッ
ダ中の UB ノードにレコードが存在する場合，子ノードと同様にその UB ノード中のレコードを走査する．
図 12 右の色付き空間での範囲検索時の UART のノード遷移
を図 12 左に示す．最初に，範囲内最小のキーである 14 を持
つ UB ノードに赤色矢印のパスで遷移する．キー 14 を持つ UB

1/𝑘 𝛼

(1)

|𝑊 |
1/𝑛 𝛼
𝑛=1

Zipf データセットは Skew パラメータ（𝛼）を 0 から 1 まで変化させ，𝛼 が 0 のとき一様分布となる．USA データセットはOpenStreetMap5 から取得したアメリカの地形データ中の 2 次元点のデータセットである．Zipf データセット，USA データセッ
トともに各次元 32 ビット整数として用いる．図 13 に 2 次元で

𝛼 = 0，𝛼 = 0.3 としたときの Zipf データセットと USA データ
セットの分布を示す．

UART のハイパーパラメータとして UB ノードのページサイズが挙げられるが，本実験ではページサイズとして 8,192 バイ
トを使用する．挿入・範囲検索ともに，8,192 バイトで最良の結果を得られたため，以降の実験はページサイズを 8,192 バイ
トとする．同様に，UB 木でも最良の結果を得られたためペー
ジサイズを 8,192 バイトとする．

ノードは，その範囲が完全に検索範囲内と重複していないため，

UB ノード中の範囲内のレコードのみ収集する．その後根ノードに回帰し，根ノードは次に部分キー “012 ” の子ノードを持つが，その範囲は検索範囲と重複しないためスキップする．そして，青色矢印のパスで次に範囲と重複する UB ノードに遷移す
る．該当 UB ノードの範囲は検索範囲に完全に包含しているた
め，包含判定なしで UB ノード内全てのレコードを収集する．

(a) Zipf ( 𝛼 = 0)(b) Zipf ( 𝛼 = 0.3)(c) USA

図 13: データセットの分布

4 評価実験
2：https://github.com/boostorg/geometry

本章では，UART の挿入と範囲検索処理に注目して性能を評

3：https://github.com/libspatialindex/libspatialindex

価する．本実験は単一スレッドで行い，逐次的に命令を発行し4：https://github.com/dbgroup-nagoya-u/cpp-utility
5：https://download.geofabrik.de/スループット[MOps/s]

uart

10

ub

1

0.1
0.01

0.001

2

4

6

8 10 12 14
次元(a) Zipf(α=0) 次元数を変化

16r(boost)
1.8
1.6
1.4
1.2
1
0.8
0.6
0.4
0

r(libspatialindex)

1.2
1.1
1
0.9
0.8
0.7
0.6
0.5

0.2

0.4
0.6
0.8
Skewパラメータ：α(b) 2次元Zipf スキューパラメータを変化

uart

ub

r(boost)(c) USA

図 14: 挿入のスループット

uart

100

ub
60

r(boost)r(libspatialindex)
60

50

50

1

40

40

0.1

30

30

0.01

20

20

0.001

10

10

0.00010

スループット[Mrecords/s]

10

2

4

6

8 10
次元

12

(a) Zipf(α=0) 次元数を変化

14

16

0

0.2

0.4

0.6

0
0.0001% 0.0010% 0.0100% 0.1000% 1.0000%

Skewパラメータ：α(b) 2次元Zipf スキューパラメータを変化

選択率(c) USA 選択率を変化

図 15: 範囲検索のスループット

4. 1 挿入

本節では，各索引構造の挿入のスループットの実験結果を紹介する．スループット測定前のデータ数は 1,000 万点であり，て，UART のスループットが最高であった．また，全ての設定
で UART のスループットは UB 木を上回り，空間分割による範囲検索の効率化を確認できた．

挿入回数は 100 万回である．図 14 に，各設定での挿入のスルー

図 15(a) に選択率 0.01%，Zipf データセット（Skew パラメー

プットを示す．全ての設定において，UART のスループットがタ：𝛼 = 0）において次元数を変化させた時の範囲検索のスルー最高となった．

プットを示す．全ての次元において，UART のスループットが

図 14(a) に Zipf データセット（Skew パラメータ：𝛼 = 0）にお最高であった．UART は 16 次元において高次元での性能劣化

いて次元数を変化させた時の挿入のスループットを示す．UART

が一番大きくなった．これは，次元数が大きくなったことで検は 16 次元において 2 次元のスループットの 0.8 倍ほどで，高次索範囲との階層的な包含判定の効果が低くなったこと，および元での性能劣化に一番頑健であった．UART と UB 木は，Z 値

1 レコードあたりのサイズが増えることでノード分割が多発しをキーとして扱うため，R∗ 木のような空間を直接扱う索引よ

木全体の構造が非平衡に崩れていったことが原因として考えらりも高次元での性能劣化が小さくなったと考えられる．

れる．

図 14(b) に 2 次元，Zipf データセットで 𝛼 を変化させた時の図 15(b) に 2 次元，選択率 0.01%，Zipf データセットで Skew

挿入のスループットを示す．UART は UB 木や R∗ 木と比較し，パラメータを変化させた時の範囲検索のスループットを示す．𝛼

データの分布が性能に大きく影響する結果となった．UART はが 0 の時と 0.5 以上の時，UART の性能が最高となった．UART

データ分布の偏り大きくなるほどプレフィックスを共有しメモの木の構造はデータの分布に大きく影響し，特に 𝛼 が 0.05 か

リ効率が良くなるため，𝛼 が 0.1 から 0.5 の時に性能が向上しら 0.4 の時はレコード数の少ない UB ノードが大量に作成された．𝛼 が 0.5 より大きい時に性能が減少したのは，データの偏ることで性能が低下したと考えられる．

りが大きくなり，木の深さが大きくなったためだと考えられる．

図 15(c) に USA データセットで選択率を変化させた時の範図 14(c) に USA データセットでの挿入のスループットを示す．

囲検索のスループットを示す．全ての選択率において，UART

UART の性能は UB 木の 1.04 倍，R∗ 木の 2.1 倍ほどであった．

のスループットが最高であった．R∗ 木は選択率 1%以降において性能が減少するのに対し，UART は常に上昇傾向であった．

4. 2 範 囲 検 索
本節では，各索引構造の範囲検索のスループットの実験結果を紹介する．スループット測定前のデータ数は 1,000 万点でUART は検索範囲の境界のノードのみで範囲内判定をする必要があるため，検索範囲が大きくなるほど性能が向上したと考えられる．

あり，範囲検索の実行回数は 1 万回である．なお，スループッ

図 16 に選択率 0.01%，Zipf データセット（𝛼 = 0）の各次元

トは一秒あたりの範囲検索結果のレコード数を示す．図 15 に数で，検索条件に 2 次元のみを使用した時の範囲検索のスルー

各設定での範囲検索のスループットを示す．多くの設定においスループット[Mrecords/s]uartr(boost)uart(all dim)

100
10
1
0.1
0.01
0.001
0.0001ub2
r(libspatialindex)
ub2(all dim)

利用することで，同じく Z 値をキーとする UB 木よりも範囲検索に特化することを実験により確認した．一方で，範囲検索に最適化した R∗ 木と同等の範囲検索性能で，挿入性能では上回ることを確認できた．したがって，UART は幅広いデータセッ
トにおいて挿入・範囲検索ともに高性能であり，汎用的に使用可能な多次元索引であると考えられる．
今後の課題として，データセットの偏りによって不安定にな

2

4

6

8

10
次元

12

14

16

図 16: 2 次元の検索条件での次元の変化による範囲検索のスループット

る性能の解消が挙げられる．また，UART の元となった ART の同時実行制御の手法 [15] を取り入れ複数スレッドに対応すること，バウンディングボックスを用いることで点データだけでなくポリゴンデータにも対応すること [9] が挙げられる．

プットを示す．検索条件に使用する次元は一様にランダムに選択し，それ以外の次元は全ドメインを検索範囲とした．なお，

謝辞

図中点線は UART と UB 木の全次元を検索範囲としたときの本研究は JSPS 科研費 JP20K19804，JP21H03555，JP22H03594

スループットである．libspatialindex の R∗ 木は 4 次元以上にの助成，および国立研究開発法人新エネルギー・産業技術総合も対応しているが，実行時間が長くなりすぎたため省略する．

開発機構（NEDO）の委託業務（JPNP16007）の結果得られた全ての次元において，UART が最高のスループットとなった．

ものである．

UART および UB 木は安定した性能であるのに対し，boost・
libspatialindex ともに R∗ 木は 3 次元において急激に性能が悪化
した．

5 関連研究本章では，UART と同じくトライ木ベースの多次元索引として PATRICIA hypercube tree（PH 木） [13] と，adaptive celltrie(ACT) [9] を紹介する．
PH 木は，ART と同様に冗長なノードを圧縮したトライ木である PATRICIA 木 [14] を多次元索引に拡張したものである．PH
木は 𝑘 次元データの Z 値を 𝑘 ビットずつ分割し，PATRICIA 木に適用して多次元拡張する．Z 値を 𝑘 ビットずつ分割すること
で，部分キーには各次元のビットを 1 ビットずつ保存する．各
ノードは最大 2 𝑘 個の子ノードを持つが，その充填率によって2 種類のノードを使い分ける．範囲検索では，各ノード下の部
分空間で，範囲内最小・最大値の計算や検索範囲の包含判定をすることで効率化する．PH 木は次元数が増加すると，各ノードのサイズが指数的に大きくなり，挿入性能が悪化する．

ACT は ART にヒルベルト曲線や Z 曲線によるセル ID を適用することで，空間結合を効率的に処理する索引構造である．

UART 同様，キーを 8 ビットずつ分割することで，空間を階層的にグリッド分割する．ACT では多角形の参照を，その領域と重複する空間を持つセル ID に保存する．空間結合処理では問合せ点の集合が与えられ，各点に対応する多角形を索引から検索する．ACT は高速に空間結合を処理できる一方で，挿入や範囲検索などの一般的な空間問合せに対応しない．

6 おわりに本稿では，ART を範囲検索と二次索引向けに最適化し，多次
元索引に拡張した UART を提案した．また，実験によりその性能を測定した．UART はノードの空間分割の特性を範囲検索に文

献[1] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger, “The R*Tree: An eﬃcient and robust access method for points and rectangles,”in Proc. SIGMOD, pp. 322–331, 1990.
[2] J. Qi, G. Liu, C. S. Jensen, and L. Kulik, “Eﬀectively learning spatial
indices,” PVLDB, vol. 13, no. 12, pp. 2341–2354, 2020.
[3] J. Ding, V. Nathan, M. Alizadeh, and T. Kraska, “Tsunami: A learned
multi-dimensional index for correlated data and skewed workloads,”
PVLDB, vol. 14, no. 2, pp. 74–86, 2020.
[4] 北川 博之, データベースシステム. 昭晃堂, 1996.
[5] R. Bayer, “The universal B-tree for multidimensional indexing: General concepts,” in Proc. Worldwide Computing and Its Applications(WWCA), pp. 198–209, 1997.
[6] P. Rigaux, M. Scholl, and A. Voisard, Spatial Databases with Application to GIS. Morgan Kaufmann, 2001.
[7] V. Leis, A. Kemper, and T. Neumann, “The adaptive radix tree: ARTful indexing for main-memory databases,” in Proc. ICDE, pp. 38–49,
2013.
[8] A. Kemper and T. Neumann, “HyPer: A hybrid OLTP&OLAP main
memory database system based on virtual memory snapshots,” inProc. ICDE, pp. 195–206, 2011.
[9] A. Kipf, H. Lang, V. Pandey, R. A. Persa, C. Anneser, E. T.
Zacharatou, H. Doraiswamy, P. A. Boncz, T. Neumann, and A. Kemper, “Adaptive main-memory indexing for high-performance pointpolygon joins,” in Proc. EDBT, 2020.
[10] T. Skopal, M. Krátký, J. Pokorný, and V. Snášel, “A new range queryalgorithm for universal B-trees,” Information Systems, vol. 31, no. 6,
pp. 489–511, 2006.
[11] H. Tropf and H. Herzog, “Multidimensional range search in dynamically balanced trees,” Applied Informatics, pp. 71–77, 1981.
[12] A. Guttman, “R-Trees: A dynamic index structure for spatial searching,” SIGMOD Rec., vol. 14, no. 2, pp. 47—-57, 1984.
[13] T. Zäschke, C. Zimmerli, and M. C. Norrie, “The PH-tree: a spaceeﬃcient storage structure and multi-dimensional index,” in Proc. SIGMOD, pp. 397–408, 2014.
[14] D. R. Morrison, “PATRICIA―practical algorithm to retrieve information coded in alphanumeric,” Journal of the ACM (JACM), vol. 15,
no. 4, pp. 514–534, 1968.
[15] V. Leis, F. Scheibner, A. Kemper, and T. Neumann, “The ART of practical synchronization,” in Proc. of the 12th International Workshop
on Data Management on New Hardware, pp. 1–8, 2016.