R-Tree - こども(てれび)

R-Tree を勉強します。

参考

Rtrees: Theory and Applications: この本のサンプル pdf がたぶんわかりやすい (chap.1, chap.2)
R-Trees: A Dynamic Index Structure for Spatial Searching: 原著論文

目的

与えられた矩形と交差する図形を探索する問題を考えます。window query と言うらしいです。これを効率的に実行するためのデータ構造が R-Tree です。

R-Tree の概要

R-Tree は B+-Tree の構造をしています。B+-Tree は、 leaf に要素が入っていて非 leaf の node は探索の為のインデックスのみを持っている B-Tree です、たぶん。R-Tree の leaf に入る要素は Minimum Bounding Rectangle (MBR) を持っていて、非 leaf の node は子 node の MBR 全てを包含する MBR を持っている。なので矩形が query として与えられたら、root を始点にして query と交差する MBR を持つ node だけを探索すればいいんだね。やったね。

つづく