チャンク化拡張可能配列による関係テーブルの実装

DEWS2007 A2-5
チャンク化拡張可能配列による関係テーブルの実装と評価
相羽 洋平
黒田 雅之
都司 達夫
樋口 健
福井大学大学院工学研究科〒910–8507 福井県福井市文京 3–9–1
E-mail: { aiba, kuroda ,tsuji,higuchi}@pear.fuis.fukui-u.ac.jp
あらまし 本論文では、チャンク単位で拡張を行う拡張可能配列による関係テーブルの一実装方式を提案、実装
し、空間的コストと検索時の時間的コストについて、従来の方式との比較評価を行う。我々は HORT (History
Offset implementation scheme for Relational Tables) と呼ぶ時間的・空間的コストの優れた関係テーブルの実装
方式を提案している。HORT における問題点のひとつとして、経歴・オフセット空間のオーバフローの問題があ
る。ここでは、経歴・オフセット空間を有効に使用するために、拡張可能配列の拡張を、配列要素単位で行うの
ではなく、配列要素の正方部分配列からなるチャンクを単位として行うことによりこの問題を軽減する。 評価実
験として、拡張可能配列の拡張が配列要素単位である HORT と、チャンク化 HORT による空間的コストと検索
の時間的コストを実測し、比較評価を行う。
キーワード 関係データベース 拡張可能配列 チャンク
An Implementation Scheme of Relational Tables by Extendible
Chunk-Array
Yohei AIBA, Masayuki KURODA, Tatsuo TSUJI, and Ken HIGUCHI
Graduate School of Engineering, University of Fukui Bunkyo 3–9–1, Fukui-city, Fukui, 910–8507 Japan
E-mail: { aiba,kuroda,azuma,tsuji,higuchi}@pear.fuis.fukui-u.ac.jp
Abstract
In this paper, an implementation scheme for relational tables is proposed. Our scheme employs extendible
chunked arrays. We are proposing an implementation scheme for relational tables named HORT(History Offset
implementation scheme for Relational Tables) which exhibits good performance in space and time costs compared with
conventional implementation. However, the problems of HORT include that its history-offset space will overflow when a
large scale relational table is stored. While a subarray of elements is dynamically allocated in the usual HORT, in our
scheme proposed, a subarray of chunks is allocated in order to utilize the history-offset space efficiently, Here, a chunk
means a hyper-cube shaped subset of a extendible array. Using a constructed prototype system, the space and time
performances of the usual HORT and the proposed scheme will be measured and compared.
Key words Relational Database, Extendible array, Chunk
1.ま
1. ま え が き
ストで対応するために、従来の固定サイズの配列では
近 年 の 高 度 な 情 報 化 社 会 の な か 、企 業 や 組 織 が 運 用
な く 、 拡 張 可 能 配 列 [3]-[7]の 概 念 を ベ ー ス と し て 用 い
を通じて蓄積されたデータや顧客情報などのデータを
る 。従 来 の 拡 張 可 能 配 列 の 実 装 に 対 し て 、HORT で は
分析し、意思決定や戦略思案の支援にデータベースを
経 歴・オ フ セ ッ ト 法 [1] [2] と 呼 ぶ 手 法 を 用 い て 配 列 要
活用することが多くなっている。そのため、大量のデ
素の位置情報を圧縮し、拡張可能配列内の有効要素の
ータをユーザーの問い合わせに応じて高速に検索を行
み に つ い て B + -tree に 格 納 す る こ と で 疎 配 列 問 題 を 解
うデータベースは必要不可欠なものになっている。そ
消している。しかし、この方式には関係テーブルのサ
こで我々は、関係テーブルが各カラムのカラム値の集
イズが増大するにつれ、経歴・オフセット空間が飽和
合であることに着目し、関係テーブルの各カラムを各
し、新たなカラム値を持つレコードの追加が不可能に
次元に対応付けた多次元拡張可能配列を用いて関係テ
な る と い う 欠 点 が あ る 。本 論 文 で は 、n 次 元 拡 張 可 能
ーブルを表現し、高速な検索を可能にする関係テーブ
配列をチャンクと呼ばれる各次元等サイズの n 次元
ル の 実 装 方 式 で あ る
部分配列を単位として拡張することを提案し、この経
HORT(History
Offset
implementation scheme for Relational Table)[1][2]
歴・オ フ セ ッ ト 空 間 の 狭 小 の 問 題 の 解 決 を 減 少 さ せ る 。
を 提 案 し た 。HORT で は 、新 た な カ ラ ム 値 を 持 つ レ コ
ま た HORT で は 、 拡 張 可 能 配 列 内 の 有 効 要 素 つ ま り 、
ードの追加による関係テーブルの拡張に対して、低コ
関係テーブルの全てのレコードの情報を 1 つの
B + -tree を 分 割 し て 持 た せ る こ と す る 。 こ の よ う に
教育
るレコードの数が減るため、挿入時間や検索時間のコ
医学
経済
ストを抑えることができる。以上の方式を実装し、既
３
学部
B + -tree を 分 割 す る こ と で 、１ つ の B + -tree に 格 納 さ れ
存 の DBMS で あ る postgreSQL と 配 列 要 素 単 位 で 拡 張
工学
３
経済
山田
医学
田中
２
医学
山田
伊藤
教育
伊藤
１
工学
鈴木
１ ２
ンク毎の独立性が高いことに注目して、チャンク毎に
田中
名前
０
こでチャンク単位で拡張を行う拡張可能配列が、チャ
学部
鈴木
挿入や検索の時間的コストが大きくなってしまう。そ
名前
０
に つ れ て こ の B + -tree の 高 さ が 高 く な り 、 そ れ に つ れ
田中
B + -tree に 格 納 し て い る た め 、 挿 入 レ コ ー ド が 増 え る
図 1： 多 次 元 配 列 を 用 い た 関 係 テ ー ブ ル の 実 装 例
を 行 う HORT 、 チ ャ ン ク 単 位 で 拡 張 を 行 う 本 方 式 に
ついて単一値指定検索における時間的コストを実測し、
比較評価を行う。
拡張可能配列とは、配列の拡張が必要となった時に
2. HORT の 概 要
拡張差分の領域のみを確保し、現在確保している領域
こ こ で は 、 我 々 が 提 案 し て い る HORT(History
Offset
implementation
2.2. 拡 張 可 能 配 列 を 用 い た 関 係 テ ー ブ ル の 実 装 方 式
scheme
for
Relational
はそのまま使用することを可能としたデータ構造であ
る 。n 次 元 拡 張 可 能 配 は 、図 2 に 示 す よ う に 経 歴 値 カ
Tables) と 呼 ば れ る 拡 張 可 能 配 列 の 概 念 を 用 い た 関 係
ウ ン タ と 各 次 元 に 経 歴 値 テ ー ブ ル 、ア ド レ ス テ ー ブ ル 、
テーブルの実装方式について説明する。
次元数 が 3 以上であれば係数テーブルの 2 または 3
2. 1.
1. 多 次 元 配 列 を 用 い た 関 係 テ ー ブ ル の 実 装 方 式
種類の補助テーブルを持つ。配列拡張が行われるたび
従来の関係テーブルの実装方式においては、レコー
に現在の経歴値カウンタが 1 つインクリメントされ、
ド は 挿 入 順 に 逐 次 2 次 記 憶 上 に 配 置 さ れ る た め 、次 の
その値が経歴値テーブルに順次記録される。ある次元
ような問題点がある。まず、レコードはカラム値の集
方 向 へ の 配 列 拡 張 は 、そ の 次 元 を 除 く n − 1 次 元 の 配
合 と し て 2 次 記 憶 上 に 配 置 さ れ る た め 、年 齢 や 性 別 と
列断面に相当するサイズの連続する記憶領域を動的に
いったカラムにおいては同じカラム値が重複して数多
確保し拡張可能配列に追加することによって行われる。
く 2 次 記 憶 上 に 格 納 さ れ る 。ま た 、あ る カ ラ ム 値 を 持
この n − 1 次元の連続記憶領域は通常の固定配列で
つレコードの検索を行うには、全てのレコードを主記
あ り 、部 分 配 列 と い う 。例 え ば 、現 在 の サ イ ズ が [s 1 , s 2 ,
憶 上 に 読 み 込 み 、カ ラ ム 値 を チ ェ ッ ク す る 必 要 が あ る 。
s3, s4] の 拡 張 可 能 配 列 に お い て 、 次 元 2 方 向 に 1 つ
そこで、これらの問題の対策として、多次元配列を用
配 列 拡 張 を 行 う 場 合 、サ イ ズ [s 1 , s 3 , s 4 ] の 3 次 元 部 分
いて関係テーブルを実装することが考えられる。
配列が動的に確保され、この部分配列の先頭アドレス
図 1 に 示 す よ う に 、関 係 テ ー ブ ル の 各 カ ラ ム を 多 次
をアドレステーブルの該当スロットに記録する。拡張
元配列の各次元に割り当て、カラム値を対応次元の配
可 能 配 列 が 3 次 元 以 上 の 場 合 に は 、部 分 配 列 内 の 要 素
列添字と対応付けることにより、関係テーブルの各レ
のアドレスを計算するための 1 次関数の n − 2 個の
コ ー ド を 配 列 の 1 要 素 と し て 扱 う こ と が で き る 。こ の
係数からなる係数ベクトルを部分配列毎に係数テーブ
方式では、同一カラム内において、同じカラム値を持
ル に 記 録 す る 。例 え ば 、上 記 の 部 分 配 列 内 の 要 素 (i 1 , i 3 ,
つレコードが複数あろうとも、カラム値そのものはた
i4) の ア ド レ ス は 1 次 関 数 s1s3i4 + s1i3 + i1 で 求 め ら
だ 1 つ 保 持 す る だ け で よ い た め 、カ ラ ム 値 を 保 持 す る
れ る 。こ の (s 1 s 3 , s 1 ) を 係 数 ベ ク ト ル と 呼 ぶ 。例 え ば 図
コストを削減することができる。また、レコードの検
2 に お い て 、 配 列 要 素 (3,4) の ア ド レ ス の 計 算 は 次 に
索や挿入、削除におけるレコードへのアクセスは、そ
よ う に 行 わ れ る 。ま ず 、第 1 次 元 の 添 え 字 が 3 で あ る
の多次元配列のアドレス関数を用いることにより、高
部 分 配 列 の 経 歴 値 ６ と 、第 2 次 元 の 添 え 字 が ４ で あ る
速に行うことができる。しかし、このような多次元固
部分配列の経歴値８を比べ、６＜８であるので、要素
定配列を用いて実装された関係テーブルに新たなカラ
(3,4)は 、経 歴 値 ８ の 部 分 配 列 に 含 ま れ る 。ま た 、こ の
ム値を含むレコードを挿入するには、そのカラムが割
部 分 配 列 の 先 頭 ア ド レ ス は 63 で あ り 、 要 素 (3,4)は 部
り当てられている次元のサイズを 1 つ増加させた多次
分 配 列 内 で は 要 素 (3) で あ る た め 、 求 め る ア ド レ ス は
元配列の領域を確保し、全配列要素を再配置するとい
66 と な る 。こ の 拡 張 可 能 配 列 を 用 い て 関 係 テ ー ブ ル を
った高コストな処理が必要となる。また、多次元配列
実装することにより、新たなカラム値を含むレコード
が大きなものとなるほどこのコストは増大する。そこ
の追加による配列の拡張を低コストで処理することが
で、任意次元方向に低コストで拡張を行うことができ
できる。
る拡張可能配列を用いることとする。
第１次元
経歴値
カウンタ
0
経歴値
10
先頭アドレス
1
4
6
の変換を高速に行うため、関係テーブルの各カラムに
7
9
CVT(key-subscript ConVersion Tree)と 呼 ぶ B + -tree
10 15 32 51 58
0 1 2 3 4
0
5
を配置し、カラム値をキーとして、対応する配列添字
第 ２次 元
0
10
0 10 15 32 51 58 70
2
20
1 20 21 33 52 59 71
3
24
2 24 25 34 53 60 73
5
40
3 40 41 42 54 61 74
補助テーブルとしてカラム値テーブルを設け、対応す
8
63
4 63 64 65 66 67 75
るカラム値を記録することにより行う。以後、各次元
10
82
5 82 83 84 85 86 87
の 補 助 テ ー ブ ル 群 の こ と を 、HORT テ ー ブ ル と 呼 ぶ こ
図 2 : 拡張可能配列の構造
また、配列添字からカラム値への逆変換は、各次元の
と と す る 。 図 3 に HORT の 構 造 の 例 を 示 す 。
田中
工学
た関係テーブルの実装方式では、レコードの存在の有
鈴木
教育
無を表現するために、配列領域全体を確保する必要が
伊藤
医学
ある。この領域は、実装する関係テーブルのカラム数
山田
医学
や 、カ ラ ム 値 の 種 類 が 多 く な る ほ ど 巨 大 な も の と な る 。
田中
経済
さらに、一般に関係テーブルを多次元配列を用いて実
学部
こで、関係テーブルに存在しているレコードについて
のみ配列上での位置情報を保持する。一般に、多次元
配列内の要素の位置を示すには次元数だけの配列添字
CVT
経歴値
レコード
カウンタ
カラム値
医学
装すると、疎配列となるため記憶領域を浪費する。そ
RDT
教育
経済
0
0
1 工学
1
2
1 教育
2
4
2 医学
3
6
1 経済
工学
(0,0)(2,1)(4,2)(5,2) (6,0)
山田
多次元固定配列ならびに多次元拡張可能配列を用い
名前
田中
学部
鈴木
名前
伊藤
2.3.
2.3 . 経 歴 ･オ フ セ ッ ト 法
をデータとして格納することにより高速に変換を行う。
0
1
2
3
0
2
田
中
1
1
鈴
木
3
1
伊
藤
5
1
山
田
0
0
0
0
0
1
1
1
0
1
2
2
0
1
2
3
を 必 要 と す る が 、HORT で は 拡 張 可 能 配 列 の 次 元 数 に
依らず、要素が含まれる部分配列の経歴値と部分配列
図 3:HORT の 構 造
内オフセットの２つの値のみを用いて要素の位置を示
す 経 歴・オ フ セ ッ ト 法 を 用 い る 。例 え ば 、図 2 の 配 列
要 素 (3,4) の 位 置 を 経 歴 ・ オ フ セ ッ ト 法 を 用 い て 表 現
3. チ ャ ン ク 単 位 で 拡 張 を 行 う HORT の 概 要
以 下 で は 、HORT に お け る 問 題 点 の 提 起 と 、そ の 問
す る と 、要 素 (3,4) が 含 ま れ る 部 分 配 列 の 経 歴 値 は ８ ，
題点を解決するために提案するチャンク単位で拡張を
要 素 (3,4)の 部 分 配 列 内 で の 位 置 は (3)で あ る た め 、経 歴
行 う HORT に つ い て 説 明 す る 。
値が８，オフセットが３となる。また、経歴値とオフ
3.1.
3.1 . 経 歴 ･オ フ セ ッ ト 法 の 問 題 点
セットの組から配列要素の組を求めるには、経歴値か
HORT で は 、関 係 テ ー ブ ル の レ コ ー ド を 示 す 論 理 拡
ら要素が含まれる部分配列を特定し、オフセットをそ
張可能配列上での有効要素の位置を、その要素が属す
の 部 分 配 列 の 係 数 ベ ク ト ル で 順 次 除 算 す る 。HORT で
る部分配列の経歴値と、その部分配列内オフセットの
は関係テーブルのレコードを表す配列の有効要素につ
２つの値の組で表現する経歴・オフセット法を用いて
いてのみ、レコードの位置情報を表すこの２つの値の
いる。しかしこの表現方法では、部分配列内オフセッ
組 を 、 2 次 記 憶 上 に 配 置 さ れ た RDT(Real Data Tree)
トに割り当てられている記憶領域を有効に使用できな
と呼ぶ
い 。例 え ば 、経 歴 値 が 0 や 1 の 部 分 配 列 の サ イ ズ は 1
B + -tree
にキーとして挿入する。これにより、
配列実体を確保する必要がなくなり、レコードの存在
であるなど、経歴値の小さな部分配列においては、オ
情報を記録する領域を抑えることができる。以後、実
フセットを格納するための変数の取り得る値の領域を
体を持たないこの拡張可能配列のことを論理拡張可能
ほとんど使用していない。またもうひとつの問題とし
配 列 と 呼 ぶ 。 ま た 、 RDT 内 で は 、 キ ー の 上 位 バ イ ト
て 、HORT で 実 装 す る 関 係 テ ー ブ ル の カ ラ ム や そ の カ
を 経 歴 値 、下 位 バ イ ト を オ フ セ ッ ト と す る こ と に よ り 、
ラム値の種類が多くなると、経歴値またはオフセット
経歴値、次いでオフセットの順でソートされる。した
の値が格納する変数の取り得る値の上限を超えてオー
が っ て 、 同 じ 経 歴 値 を 持 つ キ ー は RDT の シ ー ケ ン
バ ー フ ロ ー が 起 こ っ て し ま う 。 経 歴 値 に 32bit、 オ フ
ス・セット上に連続して配置される。
セ ッ ト に 64bit を 割 り 当 て 、 n 次 元 論 理 拡 張 可 能 配 列
2.4.
2.4 . カ ラ ム 値 か ら 配 列 添 え 字 へ の 変 換
をなるべく各次元のサイズを均等に最大まで拡張した
関係テーブルを多次元配列で実装する場合、カラム
時 の 1 辺 の サ イ ズ 、つ ま り １ カ ラ ム 当 た り の 挿 入 可 能
値から配列添字への変換ならびに配列添字からカラム
なカラム値の種類と、本来、経歴値とオフセットの組
値への逆変換が必要となる。カラム値から配列添字へ
で 表 現 で き る ア ド レ ス 空 間 、こ の 例 で は 2 9 6 の 使 用 率
を計算すると、最もアドレス空間の使用率が高くなる
できる。従って、経歴・オフセット空間のオーバーフ
3 次 元 の 時 で も 、全 体 の 3.07％ し か 使 用 で き て い な い 。
ロ ー を 遅 ら せ る こ と が で き る 。図 5 に チ ャ ン ク 単 位 で
この時の、１カラム当たりの挿入可能なカラム値の種
拡 張 を 行 う HORT の 構 造 の 例 を 示 し ， 以 下 で そ の 概
類 は 1,431,655,766 種 類 で あ る 。 こ れ 以 降 、 次 元 が 増
要と構造について説明する。以後，チャンク単位で拡
えるにつれアドレス空間の使用率は下がり、挿入可能
張 を 行 う HORT の こ と を C-HORT と 呼 ぶ こ と と す
な カ ラ ム 値 の 種 類 も 少 な く な る 。 例 え ば 10 次 元 の 時
る。
の 空 間 使 用 率 は 3.00*10 - 6 ％ で 、１ カ ラ ム 当 た り の 挿 入
を要素単位で拡張を行うのではなく、ある一定要素の
塊であるチャンク単位で拡張を行うことにより、経歴
値とオフセットの組で表現できるアドレス空間をより
有効に使えるようにする。
経歴値
先頭チャンク
番号
0
3.2.
3.2 . チ ャ ン ク 単 位 で 拡 張 を 行 う 拡 張 可 能 配 列
27
28
0
25
20
ある一定要素の塊であるチャンクを単位として拡張
を行う拡張可能配列では、チャンク毎に拡張された順
番を表すチャンク番号を振っていく。また、拡張に際
し て は 2.2 に お け る 要 素 単 位 の 部 分 配 列 に 対 し て 、 チ
年 1
齢
1
26
30
0
0
0
4
8
1
2
3
0
5
6
7
4
9 10 11
8
0
名前
2
2
山本
こ の 問 題 の 解 決 策 の 1 つ と し て 、論 理 拡 張 可 能 配 列
年齢
27
28
25
20
26
30
高橋
田中
伊藤
鈴木
可 能 な カ ラ ム 値 の 種 類 は 138 種 類 と な っ て し ま う 。
名前
鈴木
伊藤
鈴木
田中
高橋
山本
1
2
3
5
6
7
2
9 10 11
12 13 14 15
12 13 14 15
0
4
8
1
2
3
0
5
6
7
4
9 10 11
8
1
12 13 14 15
1
2
3
5
6
7
3
9 10 11
12 13 14 15
図 4:チ ャ ン ク 単 位 で 拡 張 を 行 う 拡 張 可 能 配 列 の 実 装 例
ャンク単位の部分配列が確保される。以降この部分配
列をチャンクサブ配列と呼ぶ。この時、拡張の順番を
3.3.
3.3 . CC - HORT の 構 造
示す経歴値とそのチャンク部分配列内の先頭チャンク
C-HORT に お け る 各 次 元 の HORT テ ー ブ ル は 、チ
の 番 号 を HORT テ ー ブ ル に 持 た せ る 。図 4 に 、関 係 テ
ャンク部分配列の情報を記録するチャンク情報テーブ
ーブルをチャンク単位で拡張を行う拡張可能配列で表
ルと、カラム値の情報を記録するためのカラム値情報
現した例を示す。
テーブルの２つに分けられる。チャンク情報テーブル
関係テーブルをチャンク単位で拡張を行う拡張可能
はチャンク部分配列ごとに作成され、経歴値やチャン
配列で表現すると、拡張可能配列内でのレコードの位
ク部分配列内の先頭チャンク番号とチャンク数、係数
置情報を、各チャンクに一意にふられたチャンク番号
ベクトルが格納される。また、カラム値情報テーブル
と、チャンク内オフセットの２つの値を用いて表現す
はカラム値ごとに作成され、カラム値とレコードカウ
る。チャンクのサイズを、チャンク内オフセットに割
ンタが格納される。なお、全てのチャンクのサイズを
り当てられた変数が取り得る最大値に近づけることで、
同一とすることにより、チャンク内オフセットを求め
経 歴・オ フ セ ッ ト 空 間 の 使 用 率 を 上 げ る こ と が で き る 。
る た め の 係 数 ベ ク ト ル は C-HORT に 唯 一 保 持 す る だ
要素単位で拡張を行った時と同様に、チャンク番号に
け で よ い 。ま た 、HORT で は カ ラ ム 値 毎 に 保 持 し て い
32bit，チ ャ ン ク 内 オ フ セ ッ ト に 64bit を 割 り 当 て 、 n
た 部 分 配 列 の 経 歴 値 と 係 数 ベ ク ト ル を 、C-HORT で は
次元論理拡張可能配列をなるべく各次元のサイズを均
チャンク部分配列毎に保持するだけでよくなるため、
等 に 最 大 ま で 拡 張 し た 時 の 1 辺 の サ イ ズ と 、本 来 、チ
空間的コストを抑えることができる。
ャンク番号とチャンク内オフセットの組が表現できる
3.4. 配 列 添 字 の 組 か ら チ ャ ン ク 番 号 と チ ャ ン ク
内オフセットへの変換
空間の使用率を計算する。3 次元の時は、アドレス空
間 の 使 用 率 は 99.9％ と な り 、 1 カ ラ ム 当 た り の 挿 入 可
チャンク単位で拡張される n 次元論理拡張可能配列
能 な カ ラ ム 値 の 種 類 は 4,294,529,957 種 類 、10 次 元 の
の あ る 要 素 の 添 字 が (i 1 , i 2 , ・ ・ ・ , i n )、 チ ャ ン ク の 各
時 は 、 ア ド レ ス 空 間 の 使 用 率 は 89.7％ と な り 、 1 カ ラ
辺 の サ イ ズ が (c 1 , c 2 , ・・・ , c n )で あ っ た と す る と 、各
ム 当 た り の 挿 入 可 能 な カ ラ ム 値 の 種 類 は 768 種 類 ま で
次 元 の チ ャ ン ク 情 報 テ ー ブ ル の 添 字 は (⌊i 1 /c 1 ⌋,
増える。この様に、チャンク単位で論理拡張可能配列
⌊i 2 /c 2 ⌋, ・ ・ ・ , ⌊i n /c n ⌋ )で 求 め ら れ る 。最 も 大 き な
を拡張しチャンク番号とチャンク内オフセットの２つ
経歴値を持つチャンク部分配列内に目的の要素が含ま
の値を用いてレコードを表現することにより、経歴・
れているので、この添字を基に各次元のチャンク情報
オフセット空間の使用率が低いという問題を解決する
テーブルにアクセスし、経歴値を比較することで、的
ことができる。経歴・オフセット空間の使用率を上げ
の要素が含まれるチャンク部分配列を特定することが
ることにより、従来の要素単位で拡張を行った時より
できる。次に、そのチャンク部分配列の係数ベクトル
も 1 カラムあたりのカラム値の種類を増やすことが
と、各次元のチャンク情報テーブルの添字とチャンク
部分配列内の先頭チャンク番号を用いて目的の要素が
カ ラ ム 値 を CVT を 用 い て 配 列 添 字 に 変 換 し 、 そ の 組
含まれているチャンクの番号を計算することができる。
をチャンク番号とチャンク内オフセットの組に変換、
また、このチャンクにおける目的の要素の添字は
そ の 組 を RDT か ら 削 除 す る 。 次 い で 、 削 除 し た レ コ
（ i 1 %c 1 , i 2 %c 2 , ・ ・ ・ , i n %c n ）で 求 め ら れ る た め 、
ードの各カラム値のレコードカウンタの値を 1 つデク
チャンクの係数ベクトルを用いてチャンク内オフセッ
リ メ ン ト し 、 0 に な れ ば 、 CVT か ら こ の カ ラ ム 値 を
トを求めることができる。また、チャンク番号とチャ
削除する。
ンク内オフセットの組をカラム値の組に逆変換する際
3.5
3. 5 . CC - HORT に お け る レ コ ー ド の 検 索
には、まず、そのチャンクが含まれているチャンク部
C-HORT に お け る レ コ ー ド の 検 索 は 、 RDT に 格 納
分配列の係数ベクトルを用いてチャンクのチャンク部
されているチャンク番号とオフセットの組に対して行
分配列内での添字、すなわち各次元のチャンク情報テ
わ れ る 。HORT に お け る レ コ ー ド の 検 索 と 同 様 に 、検
ーブルの添字を求める。次に、チャンクの係数ベクト
索条件として、1 つのカラムにおいてカラム値が 1 つ
ルを用いてチャンク内オフセットからチャンク内での
指定された場合の単一値指定検索における検索手法を
要素の添字を求め、これらを基に各次元のカラム値情
説 明 す る 。ま ず 、カ ラ ム 値 を 指 定 さ れ た カ ラ ム の CVT
報テーブルにアクセスすることによりカラム値を求め
を探索して論理拡張可能配列の添字に変換し、さらに
る。このように、配列添字の組からチャンク番号とオ
カラム値をチャンク情報テーブルの添字とカラム値情
フセットの組への変換ならびに逆変換時の計算コスト
報テーブルの添字に変換する。ここで、求まった添え
は 、HORT に お い て 配 列 添 字 の 組 か ら 経 歴 値 と オ フ セ
字に対応するチャンク部分配列を基チャンク部分配列
ットの組への変換ならびに逆変換時の計算コストより
と 呼 ぶ 。 こ の 時 、 カ ラ ム 値 が CVT 内 に 存 在 し な け れ
も大きくなる。
ば 、指 定 さ れ た カ ラ ム 値 を 持 つ レ コ ー ド は 存 在 し な い 。
20
CVT
年齢
26
27
28
30
(0,0)(0,5)(0,8)(0,14)(1,3)(3,4)
0
1
2
3
27
28
25
20
1
1
1
1
4 26 1
5 30 1
6
7
2
田
中
1
3
高
橋
1
山本
経歴値
1
伊
藤
1
田中
レコード
カウンタ
25
RDT
鈴木
カラム値
0
鈴
木
2
次 に 、 そ れ ら の 添 字 を 基 に RDT 内 の 検 索 を 行 う が 、
高橋
年齢
27
28
25
20
26
30
伊藤
名前
鈴木
伊藤
鈴木
田中
高橋
山本
CVT
名前
4 5 6 7
山
本
1 0 0 0
0
2
0
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
0
4
8
12
1
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
0
1
1 2 3
5 6 7
9 10 11
13 14 15
2
3
図 5:C-HORT の 構 造
その検索方法として以下の３種類の方法を考える。な
お、検索条件として指定されたカラム値のレコードカ
ウンタの値だけの検索対象レコードが見つかった時点
で検索を終了する。
3.5
3. 5 .1.
.1 . 検 索 方 法 1
まず、基チャンク部分配列の先頭チャンク番号とチ
ャ ン ク 内 オ フ セ ッ ト 0 を キ ー と し て RDT を ル ー ト ノ
ードから探索し、基チャンク部分配列内の先頭レコー
ド を 取 り 出 す 。 そ の 後 、 RDT の シ ー ケ ン ス ・ セ ッ ト
部を終端まで辿ることにより、基チャンク部分配列以
降に拡張されたチャンク部分配列内のレコードを全て
取り出す。取り出したレコードであるチャンク番号と
チ ャ ン ク 内 オ フ セ ッ ト の 組 か ら 、 3.4 で 説 明 し た チ ャ
3.4
3. 4 . CC - HORT に お け る レ コ ー ド の 挿 入 と 削 除
ンク番号とチャンク内オフセットの逆変換方式を用い
レコードの挿入を行う際には、まず、挿入対象のレ
て、次元の配列添字を求めることにより、検索対象の
コードの各カラム値が論理拡張可能配列の対応次元の
レコードであるかどうかを判定する。図６に、検索対
添 字 と 対 応 付 け ら れ て い る か ど う か を 、 CVT 内 を 探
象が、第 1 次元の添え字が５である場合の、論理拡張
索することによって調べる。もし、カラム値が配列添
可 能 配 列 の 検 索 範 囲 と RDT の 探 索 範 囲 の 例 を 示 す 。
字と対応付けられていなければ、現在使用されていな
3.5
3. 5 .2.
.2 . 検 索 方 法 2
い配列添字と対応付ける。この時、使用されていない
まず、基チャンク部分配列内の先頭チャンク番号と
配列添字が無ければ、論理拡張可能配列を対応次元方
チ ャ ン ク 内 オ フ セ ッ ト 0 を キ ー と し て 、 RDT を ル ー
向にチャンク単位で 1 つ拡張する。次に、挿入対象の
トノードから探索し、基チャンク部分配列内の先頭レ
レコードの各カラム値を各次元の配列添字の集合に変
コ ー ド を 取 り 出 す 。 そ の 後 、 RDT の シ ー ケ ン ス ・ セ
換し、チャンク番号とチャンク内オフセットの組に変
ット部を辿ることにより、基チャンク部分配列内のレ
換 、 そ れ を RDT に 格 納 す る 。 ま た 、 各 カ ラ ム 値 の レ
コードを全て取り出す。ただし、基チャンク部分配列
コ ー ド カ ウ ン タ を 1 つ イ ン ク リ メ ン ト す る 。 ま た 、レ
内のレコード全てが検索対象のレコードではないため、
コ ー ド の 削 除 を 行 う 際 に は 、HORT に お け る レ コ ー ド
チャンク番号とオフセットの組から検索対象の次元
の削除処理と同様に、まず、削除対象のレコードの各
レコードが存在しうるチャンクを求め、それぞれのチ
CVT
0 1 2
7
8 9 10 11
0
3
7
11
15
0
4
8
12
1 2 3
5 6 7
9 10 11
13 14 15
2
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
0 1 2
4 5 6
6 8 9 10
7 12 13 14
1
3
7
11
15
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
3
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
0 1 2
4 5 6
10 8 9 10
11 12 13 14
3
7
11
15
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
4
5
CVT
4 5 6
0 1 2
4 5 6
2 8 9 10
3 12 13 14
0
1
8
9
第2次元
3
6
7
ャンク内において検索対象要素のオフセットが連続し
第1次元
ている区間を求めることにより検索を行う。なお、全
4
てのチャンクのサイズは同じであるので、索対象要素
のオフセットが連続している区間の長さと、チャンク
内に存在しているこの区間の数は全て同じである。
5
こ の 方 法 を 用 い る こ と に よ り 、 RDT か ら 取 り 出 し
たレコードが検索対象のレコードであるかどうかを判
定する必要はなくなる。図８に、検索対象が、第 1 次
8
RDT
元の添え字が５である場合の、論理拡張可能配列の検
索 範 囲 と RDT の 探 索 範 囲 の 例 を 示 す 。
CVT
図６：検索方法 1 の例
0 1 2
かを判定する必要がある。
続いて、検索対象の次元以外の次元に属するチャン
ク部分配列のうち、基チャンク部分配列よりも大きな
索対象レコードが存在しうるチャンク内のレコードを
全て取り出し、検索対象の次元の配列添字を求め、検
理 拡 張 可 能 配 列 の 検 索 範 囲 と RDT の 探 索 範 囲 の 例 を
第2次元
検索対象が、第 1 次元の添え字が５である場合の、論
8 9 10 11
2
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
0 1 2 3
4 5 6 7
6 8 9 10 11
7 12 13 14 15
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
3
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
0 1 2 3
4 5 6 7
10 8 9 10 11
11 12 13 14 15
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
8
9
索 対 象 の レ コ ー ド で あ る か ど う か を 判 定 す る 。図 ７ に 、
7
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
4
5
CVT
経歴値を持つチャンク部分配列それぞれについて、検
4 5 6
0 1 2 3
4 5 6 7
2 8 9 10 11
3 12 13 14 15
0
1
の配列添字を求め、検索対象のレコードであるかどう
3
0
1
6
7
第1次元
4
5
8
RDT
図８：検索方法３の例
示す。
CVT
0 1 2
7
8 9 10 11
0
3
7
11
15
0
4
8
12
0 1 2
4 5 6
6 8 9 10
7 12 13 14
1
3
7
11
15
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
3
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
0 1 2
4 5 6
10 8 9 10
11 12 13 14
3
7
11
15
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
4
5
CVT
4 5 6
0 1 2
4 5 6
2 8 9 10
3 12 13 14
0
1
8
9
第2次元
3
6
1 2 3
5 6 7
9 10 11
13 14 15
2
7
0
4
8
12
1
5
9
13
3.6
3. 6 . RDT の 分 割
第1次元
以 下 で は 、C-HORT に お け る 問 題 点 の 提 起 し 、そ の
2 3
6 7
10 11
14 15
4
対策の説明を行う。
3.6
3. 6 .1.
.1 . CC - HORT の RDT に お け る 問 題
C-HORT に 限 ら ず 従 来 の HORT も 同 様 に 、 HORT
5
8
における挿入時間、検索時間において大きなコストを
占 め て い る の が 、RDT の デ ィ ス ク ア ク セ ス 時 間 で あ る 。
RDT は 1 つ の 関 係 テ ー ブ ル に 1 つ で 、全 て の レ コ ー ド
RDT
を 管 理 し て い る 。RDT は B + -tree で あ る の で 、レ コ ー
ドが増えるにつれ高さが高くなり、時間的コストが大
き く な っ て し ま う 。こ こ で 、C-HORT の 場 合 、論 理 拡
図７：検索方法２の例
張可能配列がチャンク単位で分割されていることに注
目 し て 、 チ ャ ン ク 毎 に RDT を 持 た せ る こ と で こ の 問
3.5
3. 5 .3.
.3 . 検 索 方 法 3
まず、基チャンク部分配列内の検索を行う。基チャ
題を減少させる。
3.6
3. 6 .2.
.2 . RDT の 分 割
ンク部分配列内には、非検索対象要素が含まれている
図 ９ に RDT を チ ャ ン ク 毎 に 分 割 し た 例 を 示 す 。RDT
ため、検索対象要素のオフセットが連続している区間
を チ ャ ン ク 毎 に 分 割 す る こ と に よ り 、1 つ の RDT に 挿
を求め、検索を行う。
入 さ れ る レ コ ー ド の 数 が 少 な く な る た め 、 B + -tree の
次に、検索対象の次元以外の次元に属するチャンク
高さが低くなり、挿入時間や検索時間が早くなると考
部分配列のうち、基チャンク部分配列よりも大きな経
え ら れ る 。 ま た 、 チ ャ ン ク 毎 に RDT を 持 た せ る こ と
歴値を持つチャンク部分配列それぞれについて検索を
により、チャンク番号とチャンク内オフセットの２つ
行 う 。C-HORT に お け る 検 索 方 法 2 と 同 様 に 検 索 対 象
の値で表されていたレコードの位置情報を、チャンク
内 オ フ セ ッ ト の み で 表 す こ と が で き る た め 、RDT の 空
RDT を ル ー ト ノ ー ド か ら 辿 る 回 数 は 、最 大 n-1 次 元 ス
間的コストも抑えることができる。
ラ イ ス の 断 面 に 存 在 す る チ ャ ン ク 個 数 で あ る 。例 え ば 、
ま た 、 検 索 に つ い て は 、 3.5 で 述 べ た 方 法 を ほ ぼ そ
該 当 の 関 係 テ ー ブ ル に お い て は 、HORT の 場 合 カ ラ ム
の ま ま 使 え る が 、RDT が チ ャ ン ク 毎 に 分 割 さ れ て い る
値 毎 に 部 分 配 列 を 持 っ て い る の で 、 124,996 個 の 部 分
ため、検索方法１に相当する検索方法は存在しない。
配 列 が 存 在 す る 。RDT を ル ー ト ノ ー ド か ら 辿 る 最 大 回
28
30
次 元 ス ラ イ ス の 断 面 に 存 在 す る チ ャ ン ク 数 は 4 4 で 256
カラム値
レコード
カウンタ
経歴値
0
1
2
3
27
28
25
20
1
1
1
1
4 26 1
5 30 1
6
7
0
1
0
鈴
木
2
1
伊
藤
1
2
田
中
1
3
高
橋
1
4 5 6 7
山
本
1 0 0 0
0
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
0
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
1
2
0
4
8
12
1 2 3
5 6 7
9 10 11
13 14 15
2
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
3
RDT_０
個 と な る の で 、RDT を ル ー ト ノ ー ド か ら 辿 る 最 大 回 数
(0) (5) (8) (14)
は 256 回 と な る 。シ ー ケ ン ス ･セ ッ ト 部 を 辿 る よ り も 、
RDT_１
(3)
ルートノードから辿るコストの方が高いので、ルート
ノ ー ド か ら 辿 っ た 回 数 が 少 な く な る C-HORT の 検 索
のコストが小さくなった。
RDT_２
postgreSQL
HORT
C-HORT
8
7
RDT_３
(4)
図 ９ ： C-HORT に お い て RDT 分 割 の 例
検索時間[秒]
27
合 は 、各 次 元 の 一 辺 の チ ャ ン ク の 数 は 4 個 で あ り 、n-1
山本
26
田中
CVT
年齢
数 は 124,996 回 と な る 。そ れ に 対 し て 、C-HORT の 場
CVT
名前
高橋
25
鈴木
20
伊藤
名前 年齢
鈴木 27
伊藤 28
鈴木 25
田中 20
高橋 26
山本 30
6
5
4
3
2
1
0
100万件
4. 比 較 評 価
以 下 で は 、 HORT, C-HORT を 実 装 し 、 HORT と
500万件
図 10： 単 一 値 指 定 検 索 の 比 較
C-HORT に お い て 、空 間 的 コ ス ト お よ び 時 間 的 コ ス ト
の 実 測 値 を 比 較 評 価 す る 。た だ し 、RDT は 2 次 記 憶 上
4.2. CC - HORT に お い て 、 RDT 分 割 前 後 の 比 較
に 配 置 し 、 CVT お よ び HORT テ ー ブ ル は 比 較 的 小 さ
int 型 の カ ラ ム , カ ラ ム 数 5, 各 カ ラ ム の カ ラ ム 値 の
いために実行時に 2 次記憶上の原本をメモリ上にロー
種 類 20,000 で あ る 関 係 テ ー ブ ル を C-HORT で 表 現 し 、
ドして使用している。
レ コ ー ド を 500 万 件 挿 入 し た 時 の RDT 分 割 前 後 に お
実 行 環 境 は 、 Sun Fire E4900 (CPU： UltraSPARC
い て 、挿 入 時 間 、RDT サ イ ズ 、検 索 速 度 の 比 較 を 表 1
IV , ク ロ ッ ク 速 度：1050MHz, メ モ リ 容 量：48 GB, デ
に示す。また、検索は検索方法２を使用する。ここで
ィ ス ク 容 量 ： RAID1 (73.4 GB×2) RAID5 (73.4 GB×
チ ャ ン ク の 一 辺 の サ イ ズ は 7131 で あ る 。
12), OS： Solaris 9)を 使 用 し た 。
4.1. P ostgreSQL、
ostgreSQL 、 HORT、
HORT 、 C - HORT と の 比 較
表 １ ： RDT 分 割 前 後 の 比 較
int 型 の カ ラ ム , カ ラ ム 数 ５ , 各 カ ラ ム の カ ラ ム 値
の 種 類 25000 で あ る 関 係 テ ー ブ ル を 、 postgreSQL
RDT 分 割 前
RDT 分 割 後
挿 入 時 間 [秒 ]
1526.54
1113.49
8.1.2、 HORT お よ び C-HORT で 表 現 し 、 レ コ ー ド を
RDT サ イ ズ [MB]
約 150
約 120
100 万 件 と 500 万 件 挿 入 し た 時 そ れ ぞ れ の 、単 一 値 指
検 索 時 間 [秒 ]
0.672
0.631
定検索において検索一件当たりの平均検索時間の比較
を 図 10 に 示 す 。 ま た 、 C-HORT の 検 索 は 検 索 方 法 ２
RDT を チ ャ ン ク 毎 に 分 割 す る と 、挿 入 の コ ス ト は 約
を 使 用 す る 。こ こ で 、C-HORT の チ ャ ン ク の 一 辺 の サ
3 分 の 1 と な っ た 。こ れ は 3.6 で 説 明 し た よ う に 、RDT
イ ズ は 7131 で あ る 。
既 存 の DBMS で あ る postgreSQL と 比 べ 、 HORT
を 分 割 し た こ と に よ り 、RDT 分 割 前 の 時 と 比 べ 、そ れ
ぞ れ の RDT の 高 さ が 低 く な っ た た め で あ る 。 今 回 の
の検索時間は約半分になっていることがわかる。さら
関 係 テ ー ブ ル の 挿 入 時 に お い て 、RDT の 高 さ の 平 均 は 、
に 、 C-HORT の 検 索 コ ス ト は HORT と 比 べ 約 5 分 の
RDT 分 割 前 が 2.9765 だ っ た の に 対 し て 、RDT 分 割 後
１ と な っ た 。こ れ は 、HORT の 拡 張 可 能 配 列 が 要 素 毎
は 1.9752 と な り 、 挿 入 時 間 の 比 と 近 い 値 と な っ た 。
に拡張を行うため、大量のデータが挿入されると部分
ま た 、RDT の キ ー 値 が 、チ ャ ン ク 番 号 と チ ャ ン ク 内 オ
配列の数が非常に多くなるため、それに比例して検索
フセットの２つの値からチャンク内オフセットのみに
時 に RDT を ル ー ト ノ ー ド か ら 辿 る 回 数 が 多 く な る か
な っ た こ と に よ り 、RDT の 空 間 的 コ ス ト も 小 さ く な っ
ら で あ る 。そ れ に 対 し て 、C-HORT の 場 合 、検 索 時 に
た 。し か し 、検 索 時 間 は 、RDT を 分 割 し て も そ れ ほ ど
減 少 し て い な い 。こ れ は 、RDT の 高 さ が 低 く な る こ と
40
で コ ス ト が 小 さ く な る の は 、RDT を ル ー ト ノ ー ド か ら
35
辿るコストだからである。挿入時は、1 つのレコード
め 、高 さ が 低 く な る こ と で 大 幅 に 時 間 を 短 縮 で き た が 、
検 索 に お い て は 、 そ れ ぞ れ の RDT 毎 に 、 一 度 ル ー ト
30
検索時間[秒]
の 挿 入 の 度 に RDT を ル ー ト ノ ー ド か ら 辿 っ て い る た
25
20
15
ノ ー ド か ら 辿 り 、そ の 後 は シ ー ケ ン ス ･セ ッ ト 部 を 辿 っ
10
て検索しているため、検索時間はそれほど短縮されな
5
かったと考えられる。
0
div_method2
div_method3
method1
method2
method3
1%
10%
20%
4.3. 検 索 方 法 に つ い て の 比 較
RDT 分 割 前 の C-HORT の 検 索 方 法 1~3 と RDT 分
30%
充填率
40%
50%
60%
図 11:充 填 率 の 変 化 さ せ た 時 の 、
割 後 の 検 索 方 法 2~3 に お い て 、充 填 率 を 変 化 さ せ た 時
検索時の時間的コストの変化
の、単一値指定検索一件当たりの平均検索時間の変化
最も大きな問題点である経歴・オフセット空間の狭小
の 比 較 を 図 11 に 示 す 。こ こ で 、語 頭 に ”div_” と 付 い
の問題を解決した。
て い る の が RDT を 分 割 し た C-HORT で あ る 。
拡張可能配列におけるレコードの位置情報をその要素
さ ら に 、 従 来 の HORT で は 、
検 索 条 件 は 、int 型 の カ ラ ム , カ ラ ム 数 ４ , 各 カ ラ ム
が含まれる部分配列の経歴値と部分配列内オフセット
値 の 種 類 80 で あ る 関 係 テ ー ブ ル を チ ャ ン ク の 一 辺 の
の２つの値を用いて表現していたが、提案した方式で
サ イ ズ を 16 と し た C-HORT で 表 現 し て 測 定 し た 。
は 、RDT を チ ャ ン ク 毎 に 持 た せ る こ と に よ り 、チ ャ ン
検索方法１については、他の検索方法と比べほとん
ク内オフセットの１つのみの値で表現している。本方
どの場合で検索時間が長い。また、充填率が上がるに
式の利点は、チャンク内オフセットを用いてレコード
つれ検索時間の増大が、他の検索方法より顕著に見ら
を表現するため、より大規模な関係テーブルの実装が
れる。検索方法１は、基チャンク部分配列以降に拡張
可 能 に な っ た こ と で あ る 。ま た 、以 上 の 方 式 を 実 装 し 、
されたチャンク部分配列内のレコードを全て取り出し
従 来 の HORT と 提 案 し た 実 装 方 式 の 空 間 的 コ ス ト と
て一致するかを判別しているため、かなり広範囲を検
検索時の時間的コストの比較を行い、本方式が有効で
索しているためである。検索方法２と検索方法３の検
あることを示した。
文
索時間については、充填率が低い場合では検索方法２
献
の 方 が 短 い が 、 充 填 率 20％ 付 近 を 境 に 逆 転 し て い る 。
[1] Masayuki Kuroda, Naoki Azuma, K. M. Azharul
検索方法２は検索方法３と比べ、論理拡張可能配列内
Hasan,Tatsuo
Tsuji,
Ken
Higuchi,
“
An
で 検 索 さ れ る 範 囲 は 広 い が 、RDT を ル ー ト ノ ー ド か ら
Implementation Scheme of Relational Tables”, Proc.
辿 る 作 業 を 減 ら し 、シ ー ケ ン ス ･セ ッ ト 部 を 多 く 辿 っ て
of ICDE 2005 Workshop, p. 1244,2005.
いる。逆に検索方法３は、論理拡張配列内の検索され
る 範 囲 は 狭 い が 、RDT を ル ー ト ノ ー ド か ら 辿 る 作 業 が
多 く な っ て い る 。RDT は ル ー ト ノ ー ド か ら 辿 る 作 業 の
方 が シ ー ケ ン ス ･セ ッ ト 部 を 辿 る 作 業 よ り コ ス ト が 大
きいため、充填率が低い場合は、検索範囲の大きい検
[2] K. M. Azharul Hasan, Masayuki Kuroda, Naoki
Azuma, Tatsuo Tsuji, Ken Higuchi, “ An Extendible
Array Based Implementation of Relational Tables
for Multi Dimensional Databases” , DaWaK 2005,
LNCS 3589, pp. 233-242, 2005.
[3] A. L. Rosenberg, “ Allocating Storage for Exte
索方法２が検索時間は短い。しかし、充填率が上がる
-ndible Array’s”, JACM, Vol. 21, pp.652-670, 1974.
と 、検 索 方 法 ２ の シ ー ケ ン ス ･セ ッ ト 部 を 辿 る 回 数 が 増
[4] A. L. Rosenberg, L. J. Stockmeyer, “ Hashing
し、検索方法３のルートノードから辿るコストを上回
Schemes for Extendible Arrays ” , JACM, Vol.24,
るため検索時間は短くなる。
pp.199-221, 1977.
ま た 、RDT 分 割 前 後 の 検 索 方 法 ２ の 検 索 時 間 が ほ ぼ
[5] E. J. Otoo, T. H. Merrett, “ A Storage Scheme for
変 わ ら な い 理 由 は 4.2 で 説 明 し た が 、RDT 分 割 前 後 の
Extendible Array’s”, Computing, Vol.31, pp.1-9, 1983.
検 索 方 法 ３ で は RDT 分 割 後 の 方 が 検 索 時 間 は 短 く な
[6] A. Novacek, “ Using Time Stamps for Storing
っ て い る 。 こ れ は 、 検 索 方 法 ３ で は RDT を ル ー ト ノ
and Addressing Extendible Arrays ” , Computing,
ー ド か ら 辿 る 回 数 が 多 い の で 、 分 割 に よ り RDT の 高
さが低くなる恩恵を多く受けたためである。
6. ま と め
本論文では、拡張可能配列を要素単位ではなく、チ
ャ ン ク 単 位 で 拡 張 を 行 う こ と に よ り 、HORT に お け る
Vol.37 pp.303- 13, 1986.
[7] 都 司 達 夫 , 水 野 剛 , 宝 珍 輝 尚 , 樋 口 健 , “ 拡 張 可 能
配 列 の 遅 延 割 付 方 式 ” , 電 子 情 報 通 信 学 会 論 文 誌 D-I,
Vol.J86-D-I, No.5, pp.351-356, 2003.