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