|
2
|
1 \chapter{非破壊的木構造データベースJungle}
|
|
15
|
2 本章では、Jungleの基本的な解説を行う。
|
|
|
3 初めに Jungle の特徴である非破壊的木構造の説明をし、その後提供しているAPIについて述べる。
|
|
2
|
4
|
|
14
|
5
|
|
|
6 \section{非破壊的木構造}
|
|
|
7 Jungle は、非破壊的木構造という特殊な木構造を持つ。
|
|
15
|
8 本節では、破壊的木構造と非破壊的木構造の編集・メリットデメリットについて記述する。
|
|
14
|
9
|
|
|
10 \vspace{0.3in}
|
|
|
11 {\Large 破壊的木構造の編集}
|
|
|
12
|
|
|
13 \vspace{0.1in}
|
|
2
|
14 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う。
|
|
11
|
15 図\ref{fig:destractive}は破壊的木構造におけるデータ編集を表している。
|
|
2
|
16
|
|
|
17 \begin{figure}[htpb]
|
|
|
18 \begin{center}
|
|
|
19 \includegraphics[scale=0.7]{figures/destructive_tree.pdf}
|
|
|
20 \caption{破壊的木構造の編集}
|
|
|
21 \label{fig:destractive}
|
|
|
22 \end{center}
|
|
|
23 \end{figure}
|
|
|
24
|
|
|
25 破壊的木構造は、編集を行う際に木のロックを掛ける必要がある。
|
|
|
26 この時、データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり、
|
|
|
27 閲覧者がいる場合は木の走査が終わるまで書き換えを待たなければならない。
|
|
|
28
|
|
14
|
29
|
|
|
30 \vspace{0.3in}
|
|
|
31 {\Large 非破壊的木構造の編集}
|
|
|
32
|
|
|
33 \vspace{0.1in}
|
|
2
|
34 データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{fig:nondestractive})。
|
|
6
|
35 その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{fig:nondestractive}の例ではノード1・3・4は編集に関係ないため新しいルートノードから参照を行い、過去の木と共有を行っている)。
|
|
2
|
36
|
|
|
37 \begin{figure}[htpb]
|
|
|
38 \begin{center}
|
|
|
39 \includegraphics[scale=0.7]{figures/non_destructive_tree.pdf}
|
|
|
40 \caption{非破壊的木構造の編集}
|
|
|
41 \label{fig:nondestractive}
|
|
|
42 \end{center}
|
|
|
43 \end{figure}
|
|
|
44
|
|
|
45 非破壊的木構造においてデータのロックが必要となる部分は、木のコピーを作り終えた後に
|
|
|
46 ルートノードを更新するときだけである。
|
|
|
47 データ編集を行っている間ロックが必要な破壊的木構造に比べ、編集中においてもデータの読み込みが可能であるが、
|
|
|
48 書き込み時の手間は大きくなる。
|
|
|
49
|
|
14
|
50
|
|
|
51
|
|
2
|
52 \begin{figure}[htpb]
|
|
|
53 \begin{center}
|
|
|
54 \includegraphics[scale=0.7]{figures/non_destructive_merit.pdf}
|
|
|
55 \caption{非破壊的木構造による利点}
|
|
|
56 \label{fig:nondestractive_merit}
|
|
|
57 \end{center}
|
|
|
58 \end{figure}
|
|
|
59
|
|
14
|
60 また、過去の木を保持する場合、非破壊的木構造は、木の複製後編集を行う必要がある。
|
|
|
61 一方、非破壊的木構造は過去の木を上書きしないため、過去の木のルートノードを保持するだけで良い。
|
|
|
62
|
|
2
|
63 \section{NodePath}
|
|
|
64 Jungleでは、木のノードの位置を{\tt NodePath}クラスを使って表す。
|
|
|
65 {\tt NodePath}クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。
|
|
|
66 {\tt NodePath}クラスを用いて{\tt< -1,1,2,3>}を表している際の例を図\ref{NodePath}に記す。
|
|
|
67
|
|
|
68 \begin{figure}[htpb]
|
|
|
69 \begin{center}
|
|
|
70 \includegraphics[scale=0.7]{figures/nodePath.pdf}
|
|
|
71 \caption{NodePath}
|
|
|
72 \label{NodePath}
|
|
|
73 \end{center}
|
|
|
74 \end{figure}
|
|
|
75
|
|
11
|
76 \newpage
|
|
2
|
77 \section{Either}
|
|
|
78 Jungleは、失敗する可能性のある関数では返り値を{ \tt Either<A、B>}に包んで返す。
|
|
6
|
79 AにはError、Bには処理に成功した際の返り値の型が入る。
|
|
2
|
80 Eitherは、AかBどちらかの値しか持たない。
|
|
|
81 以下にEitherクラスが提供しているAPI(表\ref{EitherAPI})を記す。
|
|
|
82 \begin{table}[htb]
|
|
|
83 \begin{center}
|
|
|
84 \caption{Eitherに実装されているAPI}
|
|
|
85 \begin{tabular}{|p{15em}|p{24em}|} \hline
|
|
15
|
86 {\small{\tt boolean isA()}} & {\small EitherがAを持っているかどうかを調べる。持っている場合trueを返す。}\\ \hline
|
|
|
87 {\small{\tt boolean isB()}} & {\small EitherがBを持っているかどうかを調べる。持っている場合trueを返す。}\\ \hline
|
|
|
88 {\small{\tt A a()}} &{\small Aの値を取得する。}\\ \hline
|
|
|
89 {\small{\tt B b()}} &{\small Bの値を取得する。}\\ \hline
|
|
2
|
90 \end{tabular}
|
|
|
91 \label{EitherAPI}
|
|
|
92 \end{center}
|
|
|
93 \end{table}
|
|
|
94
|
|
6
|
95 {\tt Either<A、B>} の使い方は、{\tt isA()}を用いて関数が{\tt Error}を返していないかを調べる。
|
|
2
|
96 {\tt Error}でない場合は{\tt b()}で関数の返り値を取得する。
|
|
|
97
|
|
|
98
|
|
|
99 \section{木の生成}
|
|
6
|
100 Jungleにおける木の生成について述べる。
|
|
2
|
101 Jungleは複数の木構造を、名前を利用して作成・編集・削除を行い管理している。
|
|
6
|
102 Jungleクラスが提供している木の生成・管理を行うAPIを表\ref{jungleAPI}に記す。
|
|
2
|
103
|
|
|
104 \begin{table}[htb]
|
|
|
105 \begin{center}
|
|
|
106 \caption{Jungleに実装されているAPI}
|
|
|
107 \begin{tabular}{|p{15em}|p{24em}|} \hline
|
|
15
|
108 {\small {\tt JungleTree createNewTree(String treeName)}} &{\small Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す。} \\ \hline
|
|
|
109 {\small {\tt JungleTree getTreeByName(String treeName)}} &{\small JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す。} \\ \hline
|
|
2
|
110 \end{tabular}
|
|
|
111 \label{jungleAPI}
|
|
|
112 \end{center}
|
|
|
113 \end{table}
|
|
|
114
|
|
|
115
|
|
|
116 \section{JungleTree}
|
|
|
117 Jungleは複数の木の集合で出来ている。
|
|
15
|
118 Jungleの木は、自身の情報をTreeContext というオブジェクトに保持している。
|
|
|
119 TreeContextとは、木構造のデータ(表\ref{TreeContext1})を持つクラスである。
|
|
|
120
|
|
|
121 \newpage
|
|
|
122 \begin{table}[htb]
|
|
|
123 \begin{center}
|
|
|
124 \caption{TreeContextが保持している値}
|
|
|
125 \begin{tabular}{|l|} \hline
|
|
|
126 {\tt } 自身のルートノード\\ \hline
|
|
|
127 {\tt } 1つ前のバージョンのTreeContext\\ \hline
|
|
|
128 {\tt } 編集のログ\\ \hline
|
|
|
129 {\tt } 木のuuid \\ \hline
|
|
|
130 {\tt } 木の名前 \\ \hline
|
|
|
131 {\tt } 木のversion \\ \hline
|
|
|
132 {\tt } 木の検索に使うTraverser \\ \hline
|
|
|
133 \end{tabular}
|
|
|
134 \label{TreeContext1}
|
|
|
135 \end{center}
|
|
|
136 \end{table}
|
|
|
137
|
|
|
138 Jungle の木は、自身の木構造に編集を行う Editor や 検索に使用する Traverser を提供しており、ユーザーはそれを用いて木構造にアクセスする。
|
|
|
139 また、過去のバージョンの木に対するアクセスや、特定のノードのPathを検索する機能も持っている。
|
|
2
|
140 以下にJungleTreeクラスが提供しているAPI(表\ref{JungleTreeAPI})を記す
|
|
|
141 \begin{table}[htb]
|
|
|
142 \begin{center}
|
|
|
143 \caption{JungleTreeに実装されているAPI}
|
|
|
144 \begin{tabular}{|p{15em}|p{24em}|} \hline
|
|
15
|
145 {\small {\tt TreeNode getRootNode()}} &{\small 木のルートノードを取得する。} \\ \hline
|
|
|
146 {\small {\tt long revision()}} & {\small 木のバーションを取得する。初めは0から始まり、木への変更がCommitされる度に1上昇する。} \\ \hline
|
|
|
147 {\small {\tt JungleTreeEditor getJungleTreeEditor()}} &{\small 木へ変更を加えるEditorを取得する。}\\ \hline
|
|
|
148 {\small {\tt Either<Error, JungleTree> getOldTree(long revision)}} & {\small 引数で指定したint revisionに等しいバージョンの木を取得する。} \\ \hline
|
|
|
149 {\small {\tt InterfaceTraverser getTraverser()}} & {\small 木の検索を行うTraverserを取得する。} \\ \hline
|
|
|
150 {\small {\tt Either<Error, TreeNode> getNodeOfPath(NodePath path)}} &{\small {\tt NodePathで指定した位置と値なるノードを取得する。}} \\ \hline
|
|
|
151 {\small {\tt NodePath getNodePath(TreeNode node)}} & {\small 引数で渡したノードの位置を表す{\tt NodePath}を返す。}\\ \hline
|
|
2
|
152 \end{tabular}
|
|
|
153 \label{JungleTreeAPI}
|
|
|
154 \end{center}
|
|
|
155 \end{table}
|
|
|
156
|
|
|
157
|
|
|
158 \section{TreeNode}
|
|
|
159 Jungleの木構造は、複数のノードの集合で出来ている。
|
|
|
160 ノードは、自身の子のListと属性名と属性値の組でデータを持つ。
|
|
|
161 ノードに対するアクセスは、表\ref{TreeNodeAPI}に記述されているAPIを用いて行われる。
|
|
|
162
|
|
|
163 \begin{table}[htb]
|
|
|
164 \begin{center}
|
|
|
165 \caption{TreeNodeに実装されているAPI}
|
|
|
166 \begin{tabular}{|p{15em}|p{24em}|} \hline
|
|
15
|
167 {\small {\tt Children getChildren()}} &{\small ノードの子供を扱うChildrenオブジェクトを返す} \\ \hline
|
|
|
168 {\small {\tt Attribute getAttribute()}} &{\small ノードが保持しているデータを扱うAttribteオブジェクトを返す。} \\ \hline
|
|
2
|
169 \end{tabular}
|
|
|
170 \label{TreeNodeAPI}
|
|
|
171 \end{center}
|
|
|
172 \end{table}
|
|
|
173
|
|
|
174 Childrenクラスは表\ref{Children}に記述されたAPIを、Attributeクラスは表\ref{Attribute}に記述されたAPIを提供する。
|
|
|
175 これらを利用しノードが保持している値や、子供にアクセスする。
|
|
|
176 \begin{table}[htbH]
|
|
|
177 \begin{center}
|
|
|
178 \caption{Childrenに実装されているAPI}
|
|
|
179 \begin{tabular}{|p{15em}|p{24em}|} \hline
|
|
15
|
180 {\small{\tt int size()}} & {\small 子供の数を返す。}\\ \hline
|
|
|
181 {\small{\tt <Either Error,TreeNode> at(int num)}} &{\small ノードが持つ子供の中から、 変数{\tt num}で指定された位置にある子ノードを返す。存在しない位置を指定した場合、{\tt Error} を返す。} \\ \hline
|
|
2
|
182 \end{tabular}
|
|
|
183 \label{Children}
|
|
|
184 \end{center}
|
|
|
185 \end{table}
|
|
|
186
|
|
|
187
|
|
|
188
|
|
|
189 \begin{table}[htbH]
|
|
|
190 \begin{center}
|
|
|
191 \caption{Attributeに実装されているAPI}
|
|
|
192 \begin{tabular}{|p{15em}|p{24em}|} \hline
|
|
15
|
193 {\small{\tt ByteBuffer get(String key)}} &{\small ノードが持つ値から、属性名 {\tt key}とペアの属性値を{\tt ByteBuffer}型で返す。ノードが保持していない{\tt key}を渡した場合エラーを返す。} \\ \hline
|
|
|
194 {\small{\tt String getString(String key)}} &{\small ノードが持つ値から、属性名 {\tt key} とペアの属性値を{\tt String}型で返す。ノードが保持していない{\tt key}を渡した場合エラーを返す。} \\ \hline
|
|
2
|
195 \end{tabular}
|
|
|
196 \label{Attribute}
|
|
|
197 \end{center}
|
|
|
198 \end{table}
|
|
|
199
|
|
|
200 \newpage
|
|
14
|
201 以下にルートノードの2番目の子供から、属性名 {\tt name}とペアになっている属性値を取得するサンプルコード\ref{getAttributeCode}を記述する。
|
|
2
|
202 \begin{lstlisting}[frame=lrbt,numbers=left,label=getAttributeCode]
|
|
|
203 JungleTree tree = jungle.getTreeByName("TreeName");
|
|
|
204 TreeNode root = tree.getRootNode();
|
|
|
205 Children children = root.getChildren();
|
|
11
|
206 Either<Error,TreeNode> either = children.at(1);
|
|
2
|
207 if (either.isA())
|
|
|
208 return either.a();
|
|
|
209 TreeNode child = either.b();
|
|
|
210 Attribute attribute = child.getAttribute();
|
|
|
211 String value = attribute.getString("name");
|
|
|
212 \end{lstlisting}
|
|
|
213
|
|
14
|
214 ソースコード\ref{getAttributeCode}の説明を行う。
|
|
15
|
215
|
|
|
216 1行目で Jungle から木を取得し、
|
|
|
217 2行目で、取得した木のルートノードを取得している。
|
|
|
218 3 - 7行目でルートノードの1番目の子ノードを取得し、
|
|
|
219 8 - 9行目で、ルートの1番目の子ノードから、属性名 "name" とペアの属性値を取得している。
|
|
2
|
220
|
|
|
221 \section{木の編集API}
|
|
|
222 Jungleの木の編集は{\tt Default Jungle Tree Editor}クラスを用いて行われる。
|
|
|
223 {\tt Default Jungle Tree Editor}クラスは、木に対する編集を行うAPIが定義されているJungle Tree Editorインターフェースを実装している。
|
|
6
|
224 Default Jungle Tree Editorは、Jungle Tree から、{\tt getTreeEditor()}を用いて取得する。
|
|
2
|
225 表\ref{editor}にJungle Tree Editorインターフェースに定義されているAPIを記述する。
|
|
14
|
226 また、表\ref{editor}に記述しているAPIは全て、{\tt Either<Error,JungleTreeEditor>} を返す。
|
|
11
|
227
|
|
2
|
228 \begin{table}[htb]
|
|
|
229 \begin{center}
|
|
|
230 \caption{Editorに実装されているAPI}
|
|
14
|
231 \begin{tabular*}{\textwidth}{|p{15em}|p{22em}|} \hline
|
|
|
232 {\small\tt addNewChildAt( NodePath path, int pos)} &
|
|
15
|
233 {\small\tt path}で指定したノードの{\tt pos}番目の子の後にノードを追加する。\\ \hline
|
|
14
|
234 {\small\tt deleteChildAt( NodePath path,int pos)} &
|
|
15
|
235 {\small\tt path}で指定したノードの{\tt pos}番目の子ノードを削除する。 \\ \hline
|
|
14
|
236 {\small\tt putAttribute( NodePath path,String key,ByteBuffer value)} &
|
|
15
|
237 {\small\tt path}で指定したノードに属性名 {\tt key} 属性値 {\tt value} のペアで値を挿入する。 \\ \hline
|
|
14
|
238 {\small\tt deleteAttribute( NodePath path,String key)}&
|
|
15
|
239 {\small\tt path}で指定したノードが持つ、属性名 {\tt key}とペアで保存されている属性値を削除する。\\ \hline
|
|
14
|
240 {\small\tt moveChild( NodePath path,int num,String move)} &
|
|
15
|
241 {\small\tt path}で指定したノードの{\tt num}番目の子供を{\tt move}の方向に移動させる。 \\ \hline %あとで直す
|
|
14
|
242 {\small\tt pushPop()} &
|
|
2
|
243 ルートノードの上に新しいルートノードを追加する。線形の木を作る際に使用することで木の変更の手間をO(n)からO(1)にできる。\\ \hline
|
|
14
|
244 {\small\tt success()} &
|
|
2
|
245 木へ行った変更をコミットする。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗する。 \\ \hline
|
|
14
|
246 \end{tabular*}
|
|
2
|
247 \label{editor}
|
|
|
248 \end{center}
|
|
|
249 \end{table}
|
|
|
250
|
|
|
251
|
|
|
252
|
|
15
|
253 編集後に返される{\tt Default Jungle Tree Editor}クラスは、編集後の木構造を保持しているため、編集前の木構造を保持している{\tt Default Jungle Tree Editor}クラスとは別のオブジェクトである。
|
|
|
254 編集を行った後は、関数{\tt editor.success()}で今までの編集をコミットすることができる。他の{\tt Default Jungle Tree Editor}クラスによって木が更新されていた場合はコミットは失敗し、{\tt success()}は{\tt Error}を返す。
|
|
2
|
255 その場合は、木の編集を最初からやり直す必要がある。
|
|
|
256
|
|
|
257 以下に{\tt JungleTreeEditor}クラスを用いて、木の編集を行うサンプルコードを記述する。
|
|
|
258
|
|
|
259 \begin{lstlisting}[frame=lrbt,numbers=left,label=editorCode]
|
|
|
260 JungleTreeEditor editor = tree.getTreeEditor();
|
|
|
261 DefaultNodePath editNodePath = new DefaultNodePath();
|
|
|
262 Either<Error, JungleTreeEditor> either = editor.addNewChildAt(editNodePath, 0);
|
|
|
263 if (either.isA())
|
|
|
264 return either.a();
|
|
|
265 editor = either.b();
|
|
|
266 editor.success();
|
|
|
267 \end{lstlisting}
|
|
|
268
|
|
15
|
269 1行目で、木から Editor を取得している。
|
|
|
270 2行目で、編集を行うノードの Path を作成している。Default Node Path は、生成時はルートノードを指しているため、今回はルートノードに対する変更であることがわかる。
|
|
|
271 3行目で、実際にルートノードに対して、子ノードの追加を行っている。
|
|
|
272 4行目以降で、編集が成功したかどうかを {\tt Either }を使って確かめ、成功していた場合7行目で変更を木に Commit している。
|
|
|
273
|
|
|
274 \begin{comment}
|
|
2
|
275 \begin{enumerate}
|
|
|
276 \item 関数{\tt tree.getEditor()}で編集を行う木から、{\tt JungleTreeEditor}クラスを取得する。
|
|
|
277 \item 次に変更するノードの場所を示す、{\tt NodePath}クラスを作成する。
|
|
|
278 \item 関数{\tt editor.addNewChildAt()}を用いて、変数{\tt path}で指定したノードの子供の0番目に子ノードを追加する。
|
|
|
279 \item 返り値の変数{\tt either}が{\tt Error}クラスを保持していないか(編集に失敗していないか)を確認する。
|
|
|
280 \item {\tt Error}クラスを保持していた場合{\tt Either.a()}でErrorを返す。
|
|
|
281 \item 編集に成功していた場合、編集後木を持った、{\tt JungleTreeEditor}クラスを取得する。
|
|
|
282 \item 取得した{\tt JungleTreeEditor}クラスを用いて木の変更をコミットする。
|
|
|
283 \end{enumerate}
|
|
15
|
284 \end{comment}
|
|
2
|
285
|
|
|
286 また、木に対して行われた変更は、Logとして書き出される。
|
|
15
|
287
|
|
|
288 \section{Commit}
|
|
|
289 Jungle Tree Editor を用いて木に変更を加えた後は、Commit を行う必要がある。
|
|
|
290 Commit は、前節で記述した Jungle Tree Editor が持つ関数 {\tt success()} を使用することで行われる。
|
|
|
291
|
|
|
292 Commit を行うと、Jungle Tree Editor が保持している編集後の木構造のデータを持つ TreeContext を作成する。
|
|
|
293 そして、編集前の木が持つ TreeContext と 新しく作った TreeContext を置き換えることで Commit は完了する。
|
|
|
294 TreeContext の置き換えは、編集を行っている他の Thread と競合した際に、木の整合性を保つために以下の手順で行われる。
|
|
|
295
|
|
|
296 \begin{enumerate}
|
|
|
297 \item 新しく作った TreeContext が持つ、1つ前のバージョンの TreeContext と、編集前の木構造の TreeContext を比較する。
|
|
|
298
|
|
|
299 \item 一致しなかった場合、他のが Thread が Commit をすでに行っているため、失敗する(競合に負けた)。
|
|
|
300
|
|
|
301 \item 一致した場合、TreeContext を Atomic に入れ替える(競合に勝った)。
|
|
|
302 \end{enumerate}
|
|
|
303
|
|
|
304 競合に負けた場合は、新しい木に対してもう一度同じ変更を行う必要がある。
|
|
2
|
305 これらのAPIにより、Jungleは木構造を格納、編集する機能を持っている。
|
|
|
306
|
|
6
|
307 \section{Log}
|
|
|
308 Jungle は、 Editor を用いて木に編集を加える際、使用した API に応じて対応する NodeOperation を作成する。
|
|
|
309 NodeOperation は NodePath とペアで扱わなければならず、このペアを TreeOperation という。
|
|
|
310 Jungle によるデータの編集は TreeOperation が複数集まった単位で commit されていく.
|
|
|
311 この TreeOperation の集まりを TreeOperationLog という。
|
|
|
312 TreeOperationLogの仕様をソースコード\ref{src:treeoperationlog}に示す.
|
|
|
313 \begin{lstlisting}[frame=lrbt,label=src:treeoperationlog,caption=TreeOperationLogの仕様,numbers=left]
|
|
|
314 public interface TreeOperationLog extends Iterable<TreeOperation>
|
|
|
315 {
|
|
15
|
316 public TreeOperationLog add(NodePath _p,NodeOperation _op);
|
|
|
317 public TreeOperationLog append(TreeOperationLog _log);
|
|
|
318 public int length();
|
|
6
|
319 }
|
|
|
320 \end{lstlisting}
|
|
|
321
|
|
|
322 \verb|Iterable<TreeOperation>|を継承しているためIteratorによりTreeOperationを取り出せるようになっている。
|
|
|
323 addやappendメソッドを使ってTreeOperationを積み上げていくことができる。
|
|
|
324 積み上げたLogをディスクに書き出すことで、Jungleは永続性を持つ。
|
|
|
325 分散版Jungleでは、Logを他ノードに送ることで、データの分散を行う。
|
|
|
326
|
|
|
327
|
|
|
328
|
|
2
|
329
|
|
14
|
330 \section{検索API}
|
|
2
|
331 これまでに紹介したAPIにより、Jungleは木構造を構築できるようになった。
|
|
15
|
332 しかし、木に問い合わせを行う検索APIが実装されていなかったため、木の走査を行う{\tt Interface Traverser}クラス内に、lambda式を用いて実装した。
|
|
2
|
333 以下に検索を行う関数{\tt find}の定義を記述する。
|
|
|
334 \begin{lstlisting}[frame=lrbt,label=query,numbers=left]
|
|
|
335 public Iterator<TreeNode> find(Query query, String key, String searchValue);
|
|
|
336 \end{lstlisting}
|
|
|
337
|
|
15
|
338 関数{\tt find}は、第一引数には、探索の条件を記述する関数{\tt boolean comdition(TreeNode)}を定義した{\tt Query}を、
|
|
2
|
339 第二、第三引数には、Indexを用いた絞込に使用する{\tt String key、String value}を取り、条件に一致したノードの{\tt Iterator}を返す。
|
|
11
|
340 {\tt 関数find}の使用例を以下に記す。
|
|
2
|
341
|
|
|
342 \begin{lstlisting}[frame=lrbt,label=find,numbers=left]
|
|
|
343 InterfaceTraverser traverser = tree.getTraverser(true);
|
|
|
344 Iterator<TreeNode> resultNodeIterator = traverser.find((TreeNode node) -> {
|
|
15
|
345 String name = node.getAttributes().getString("name");
|
|
|
346 if (name == null) return false;
|
|
|
347 return name.equals("kanagawa");
|
|
|
348 }, "belong", "ryukyu");
|
|
2
|
349 \end{lstlisting}
|
|
|
350
|
|
|
351
|
|
|
352 上記コードについて解説する。
|
|
15
|
353
|
|
|
354 1行目で検索対象の木から、検索に使用する {\tt Interface Traverser} を取得する。
|
|
|
355 2行目で、検索を行う関数 {\tt find()} を使用する。
|
|
|
356 今回は、Index を使って、属性名 {\tt "belong"} 属性値 {\tt "ryukyu"} を持つノード取得し、
|
|
|
357 3 - 5行目で定義されたクエリに渡す。
|
|
2
|
358
|
|
15
|
359 そして、クエリの中で属性名 {\tt "name"} 属性値 {\tt "kanagawa"} を持つノードかどうかを確かめる。
|
|
|
360
|
|
|
361 結果として、属性名 {\tt "belong"} 属性値{\tt "ryukyu"}と、属性名 {\tt "name"} 属性値{\tt kanagawa}の2つのデータを持つノードの {\tt Iterator} が取得できる。
|
|
|
362
|
|
|
363 検索の際に使用する Index の実装については次節に記述する。
|
|
2
|
364
|
|
15
|
365 \begin{comment}
|
|
|
366 \begin{enumerate}
|
|
|
367 \item 木の走査を行う{\tt Traverser}クラスを取得する。
|
|
|
368
|
|
|
369 \item Indexから{\tt find}の第2、第3引数である、属性名 {\tt belong}、属性値 {\tt ryukyu}の組のデータを持つノードを取得し、Queryに渡す(ノードの絞込を行う)。
|
|
2
|
370
|
|
15
|
371 \item 引数のノードから関数{\tt getAttributes().getString("name")}で属性名 {\tt name}とペアになっている属性値を取得する。
|
|
|
372
|
|
|
373 \item 属性値が{\tt null}だった場合、このノードには属性名が{\tt name}の組のデータは存在しないので、{\tt false}を返し次のノードの評価を行う。
|
|
|
374
|
|
|
375 \item 属性値が{\tt null}でなかった場合、{\tt kanagawa}と一致するかどうかを調べ結果を返す。
|
|
2
|
376
|
|
|
377 \end{enumerate}
|
|
15
|
378 \end{comment}
|
|
2
|
379
|
|
|
380
|
|
14
|
381 \section{Index}
|
|
2
|
382 Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。
|
|
11
|
383 よって、全ての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。
|
|
2
|
384 既存のTreeMapでは、一度Indexの複製を行ない、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。
|
|
|
385 その問題を解決するため、非破壊TreeMapを自作し、それを用いてIndexの実装を行った。
|
|
|
386 このTreeMapは、Jungleと同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行った際、前の版と最大限データを共有した新しいTreeMapを作成する。
|
|
|
387 Jungleとの違いは、木の回転処理が入ることである。
|
|
|
388 これにより複数の版全てに対応したIndexをサポートすることが可能になった。
|
|
|
389 以下にJungleにおけるIndexの型を記述する
|
|
|
390
|
|
|
391 \begin{lstlisting}[frame=lrbt,label=index,numbers=left]
|
|
11
|
392 TreeMap<String key,TreeMap<String attribute,List<TreeNode> nodeList> index> indexMap
|
|
2
|
393 \end{lstlisting}
|
|
|
394
|
|
|
395 JungleのIndexは{\tt IndexMap}内に保持されている。
|
|
|
396 属性名で{\tt IndexMap}に{\tt get}を行うと、対応したIndexが取得できる。
|
|
|
397 取得したIndexに属性値で{\tt get}を行うと、ノードのリストが返ってくる。
|
|
|
398 以下にIndexから属性名 name 属性値 kanagawaのデータを持つ、ノードのIteratorを取得するサンプルコードを記述する。
|
|
|
399
|
|
|
400 \begin{lstlisting}[frame=lrbt,label=find,numbers=left]
|
|
|
401 Optional<TreeMap<String, List<TreeNode>>> indexOp = indexMap.get("name");
|
|
|
402 if (!indexOp.isPresent())
|
|
|
403 return new NulIterator<TreeNode>();
|
|
15
|
404 TreeMap<String, List<TreeNode>> index = indexOp.get();
|
|
|
405 Optional<List<TreeNode>> nodeListOp = index.get("kanagawa");
|
|
2
|
406 if (!nodeListOp.isPresent())
|
|
|
407 return new NulIterator<TreeNode>();
|
|
|
408 return nodeListOp.get().iterator();
|
|
15
|
409 \end{lstlisting}
|
|
|
410
|
|
|
411 1 - 4行目で IndexMap から 属性名 "name" に対する値を持つ Index を取得している。
|
|
|
412 5 - 8行目で 取得した Index から、 属性名 "kanagawa" を持つノードの{ \tt Iterator}を取得している。
|
|
2
|
413
|
|
|
414
|
|
15
|
415 \begin{comment}
|
|
|
416 \begin{enumerate}
|
|
|
417 \item {\tt indexMap}に、今回検索で使用する属性名 {\tt name}を使用して{\tt get("name")}を行う。すると属性名 {\tt "name"}に対応したIndexが、{\tt Optional}クラスで包まれて返ってくる。
|
|
2
|
418
|
|
15
|
419 \item {\tt Optional}オブジェクトに対して、中身を保持しているか(属性名 {\tt name}に対応したIndexを木が持っているか)を調べる。
|
|
2
|
420
|
|
15
|
421 \item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。
|
|
2
|
422
|
|
15
|
423 \item 持っていた場合、{\tt Optional}オブジェクトからIndexを取得する。
|
|
2
|
424
|
|
15
|
425 \item 取得したIndexに、検索で使用する属性値{\tt "kanagawa"}で{\tt get()}を行う。すると、属性名 {\tt "name"} 属性値{\tt "kanagawa"}の値を持つノードのリストが、{\tt Optional}クラスに包まれて返ってくる。
|
|
2
|
426
|
|
15
|
427 \item {\tt Optional}オブジェクトに対して中身を保持しているか(属性名 {\tt "name"} 属性値 {\tt "kanagawa"}を持つノードを木が持っているか)を調べる。
|
|
2
|
428
|
|
15
|
429 \item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。
|
|
2
|
430
|
|
15
|
431 \item 持っていた場合{\tt Optional}オブジェクトからノードリストの{\tt Iterator}を返す。
|
|
2
|
432
|
|
15
|
433 \end{enumerate}
|
|
|
434 \end{comment}
|
|
2
|
435
|
|
15
|
436 JungleはこれらのAPIにより、木構造を格納、編集、検索する機能を持っている。
|
|
2
|
437
|
|
15
|
438 \newpage
|
