Mercurial > hg > Papers > 2017 > tatsuki-master
changeset 6:498b8f4175f9
commit
| author | tatsuki |
|---|---|
| date | Wed, 01 Feb 2017 08:24:04 +0900 |
| parents | 328b6e52db10 |
| children | c1b81e802b25 |
| files | abstract.tex abstract_eng.tex differential.tex figures/EditDifferencialTree.graffle figures/EditDifferencialTree.pdf indexupdate.tex introduciton.tex jungle.tex jungleUpdatePoint.tex master_paper.tex redBlackJungleTree.tex redBlackTree.tex |
| diffstat | 12 files changed, 268 insertions(+), 250 deletions(-) [+] |
line wrap: on
line diff
--- a/abstract.tex Mon Jan 30 03:54:57 2017 +0900 +++ b/abstract.tex Wed Feb 01 08:24:04 2017 +0900 @@ -1,11 +1,10 @@ \begin{abstract} -Jungleは、本研究室で開発されている非破壊的木構造データベースである。 -Jungleは、プログラム内部に直接木構造を構築する。 -また、木の変更は、ルートをアトミックに入れ替えることでトランザクションを実現する。 +Jungleは、本研究室で開発している、プログラム内部に木構造を構築するデータベースである。 +木の変更は、変更を加えたノードから、ルートまでの経路の複製を行い、新しいルートをアトミックに入れ替えることでトランザクションを実現する。 この方法により、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する。 プログラムは、この木を内部のデータ構造として直接取り扱うことができる。 また、汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能になっている。 -しかし、木構造の形によっては、木の変更の手間が大きくなる・Indexの更新処理が極めて重いという面があった。 +%しかし、木構造の形によっては、木の変更の手間が大きくなる・Indexの更新処理が極めて重いという面があった。 本研究では、Jungleデータベースの大幅な改善を行い、既存のJungleとくらべて大幅な処理の高速化に成功した。 また、Jungleを使用した例題アプリケーションを作成し、性能測定を行ったところ、木構造の形によって処理速度に差が出ることがわかった。
--- a/abstract_eng.tex Mon Jan 30 03:54:57 2017 +0900 +++ b/abstract_eng.tex Wed Feb 01 08:24:04 2017 +0900 @@ -1,18 +1,3 @@ \begin{abstract_eng} -Users of the Wev services is increasing by the diffusion of smartphone and tablet pc. -However it caused the webserver down. -Therefore, scalability is the important software factor for Web services today. -Scalability in distributed system is able to increase performance linearly when just added new node to system. -In order to provide scalability to Web services, database must have scalability. - -For study of scalable database, we are designing and developing a database Jungle which has non-destructive tree structure. -Non-destructive tree structure dose not destruct the data when data editing by creating new tree. - -In this paper, we implemented persistent and distributed database on jungle. -Distributed data on Jungle is developed by using Alice which is parallel distributed framework. -We confirm the data distribution between the server nodes on Jungle with our cluster system. -Also, we developed simple bulletinboard system with Jungle and key-value store database Cassandra. -We compared response time of Jungle and Cassandra using simple bulletinboard. -As a result, Jungle got better performance than Cassandra. - +英語のアブスト \end{abstract_eng}
--- a/differential.tex Mon Jan 30 03:54:57 2017 +0900 +++ b/differential.tex Wed Feb 01 08:24:04 2017 +0900 @@ -1,8 +1,9 @@ \chapter{Differential Jungle Tree} Jungleの木の変更の手間は木の形によって異なる。 -に線形の木は、変更の手間がO(n)となってしまう。 +特に線形の木は、変更の手間がO(n)となってしまう。 線形の木をO(1)で変更するために、Jungleは、ルートノードを追加していくPushPopの機能を持つ。 -しかし、PushPopはルートノードを追加していくため、図\ref{fig:pushpop}のようにノードの並びが逆順になってしまうため、正順の木を構築する際は、PushPopを使用できない。 +しかし、PushPopはルートノードを追加していくため、図\ref{fig:pushpop}のようにノードの並びが逆順になってしまう。 +Logなどの正順の木でなければデータを表現できない場合、木の編集時 PushPop を使用できない。 \begin{figure}[htpb] \begin{center} @@ -36,38 +37,42 @@ \end{center} \end{table} -Differential Jungle Treeでは、現在の版の木構造の末尾ノード保持することが可能な DifferentialTreeContext 作成した。 +Differential Jungle Treeでは、現在の版の木構造の末尾ノード保持することが可能な Differential Tree Context 作成した。 +\newpage + \section{Differential Jungle Treeの作成} -Differential Jungle Treeを作成するためにJungleに、新しいAPIを実装した(表\ref{createDifferentialTree})。 -\begin{table}[htb] -\begin{center} -\caption{Jungleに新しく実装したAPI} -\begin{tabular}{|p{15em}|p{24em}|} \hline -{\tt createNewDifferentialTree} {\tt (String treeName) } & Jungleに新しくDifferential Treeを生成する。木の名前が重複した場合、生成に失敗しnullを返す。 \\ \hline -\end{tabular} -\label{TreeContext} -\end{center} -\end{table} +Differential Jungle Treeを作成するためにJungleに、{\tt createNewDifferentialTree(String treeName) }を実装した。 +これは、第一引数String {\tt treeName}で受け取った名前の Differential Tree を作成する。 +その際、名前が重複した場合木の生成に失敗する。 + ソースコード\ref{newDifferentialTree}に新しいDifferential Jungle Treeを作成するサンプルコードを記載する。 - -\begin{lstlisting}[frame=lrbt,numbers=left,label=newDifferentialTree] +\begin{lstlisting}[frame=lrbt,numbers=left,label=newDifferentialTree,caption=Differential Jungle Treeの生成] Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser()); // jungleの作成 -JungleTree tree = jungle.createNewDifferenceTree("df"); //Differential Treeの作成 +String treeName = "difTree"; //treeNameの設定 +JungleTree tree = jungle.createNewDifferenceTree(treeName]); //Differential Treeの作成 \end{lstlisting} +Jungle では、{\tt TreeMap<String,Jungle Tree>} を用いて Jungle Tree を管理している。 +Differential Jungle Tree と Default Jungle Tree は、同じ TreeMap に保持されるため、別々の木に同じ名前をつけることはできない(ソースコード\ref{src:nameFail})。 +\begin{lstlisting}[frame=lrbt,numbers=left,label=src:nameFail,caption=名前の重複] +Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser()); // jungleの作成 +String treeName = "treeName"; //treeNameの設定 +JungleTree defaultTree = jungle.createNewTree(treeName) //Default Treeの作成 +JungleTree dfTree = jungle.createNewDifferenceTree(treeName); //Differential Treeの作成 +\end{lstlisting} - +ソースコード\ref{src:nameFail}では、4行目で Differentail Jungle Tree の名前が、3行目で生成した Default Jungle Tree の名前と重複するため、木の生成に失敗する。 \section{末尾ノードを使用した木の編集} Differential Jungle Treeの木の編集は、Differential Jungle Tree Editorを使用して行う。 -Differential Jungle Tree Editorは、Jungle Tree Editor インターフェースを実装しているため、使い方はDefault Jungle Tree Editorと同じである。 +%Differential Jungle Tree Editorは、Jungle Tree Editor インターフェースを実装しているため、使い方はDefault Jungle Tree Editorと同じである。 -処理の違いは、Default Jungle TreeのEditorは、木の複製を行い、過去の木を保持するのに対して、Differential Jungle TreeのEditor は、Sub Treeを保持しており、そのSub Treeに対して破壊的に編集を行う。 -そして、Commitを行う際に、構築したSub Treeを末尾ノードにAppendすることで木の編集を行う。 -そうすることで、木の複製を行う必要が無いため、木の変更の手間はO(1)で行える。 +Default Jungle Tree との、木の編集時の処理の違いは、Default Jungle Tree の Editorは、木の複製を行い、過去の木を保持するのに対して、Differential Jungle TreeのEditor は、自身が保持している Sub Tree に対して破壊的に編集を行う。 +そして、Commitを行う際に、構築したSub Treeを末尾ノードにAppendする。 +そうすることで、木の複製を行う必要がないため、木の変更の手間はO(1)で行える。 また、Differential TreeはSub Treeに対する変更しか行えないため、一度Commitした木に対して変更は行えない。 図\ref{fig:EditDifTree}にDifferential Jungle Treeの編集の流れを記述する。 @@ -82,7 +87,7 @@ \newpage \begin{enumerate} -\item 木から{\tt getTreeEditor}でEditorを取得する。(このとき取得するEditorはSub Treeを持つ)。 +\item 木から{\tt getJungleTreeEditor}でEditorを取得する。(このとき取得するEditorはSub Treeを持つ)。 \item SubTreeに対して{\tt addNewChild(<-1,0>)}を実行し、ノードの追加を行う。 \item Commitを行い、Treeの末尾ノードにSub TreeをAppendする。 \end{enumerate} @@ -98,10 +103,11 @@ そうすることで、編集が競合した際の整合性を保っている。 -また、Differential Jungle Treeは、木を破壊的に変更する。 -よって、過去の木を取得し、変更を加えた場合、末尾ノードに複数のSub TreeがAppendされてしまい、木の整合性が崩れてしまう。 -その問題を解決するため、Differential Jungle Treeでは、末尾ノードは一つしか子ノードを持つことができない。 +また、Differential Jungle Treeは、木を破壊的に変更するため、過去の木を取得し変更を加えた場合、末尾ノードに複数のSub TreeがAppendされてしまい、木の整合性が崩れてしまう。 +その問題を解決するため、末尾ノードは1つしか子ノードを持つことができない。 +ノードのAppend時、末尾ノードが子ノードを持っていた場合、過去に木に対する変更と判断し、木の Commit は失敗する。 +\begin{comment} ソースコード\ref{src:Append}にSub TreeのAppend部分のコードを記述する。 \begin{lstlisting}[frame=lrbt,label=src:Append,caption=Sub TreeのAppend部分のコード,numbers=left] @@ -126,101 +132,14 @@ \end{enumerate} このように、末尾ノードが複数の子を持つことを禁止することで、過去の木を取得した際の木の整合性を保証している。 - -\section{Commit Operation} -Default Jungle Treeでは、木に対しての変更は全てメインの木に対する変更であるため、Logに書き出された全ての変更を一回の Commit で行える。 -しかし、Differential Jungle Treeの変更は、Editorが保持しているsubTreeに対する変更を加えた後、 Commit 時にメインの木にAppendを行っている。 -そのため、適切なタイミングでCommitを行わないと、実際に行われた変更とズレが生じて、正しい木を構築できない。 - -以下に、Logからの木の構築をする際に、一回のCommitでは適切なDifferential Treeを構築できない例を記す。 -\begin{lstlisting}[frame=lrbt,label=src:treelog,caption=適切な木を構築できないLogの例,numbers=left] -1.[APPEND_CHILD:<-1>:pos:0] -2[COMMIT] -3.[APPEND_CHILD:<-1>:pos:0] -4.[APPEND_CHILD:<-1,0>:pos:0] -\end{lstlisting} - -大文字の英字はLogとして書き出された Operation の種類を表す。 -\verb|<>| により囲まれている数字は NodePath を示す。 -NodePath の表記以降は、ノードの position などの情報を表している。 -[COMMIT]は、実際の木を構築した際にCommitが行われたタイミングを表す。 - -[COMMIT]のタイミングでCommitを行わず、全ての変更を加えた後にCommitを行った場合、Editor 内部の Sub Treeに、図\ref{fig:badDifTreeCreate}のような変更が加えられ、Append後、図\ref{fig:badDifTree}のような木が構築される。 - - -\begin{figure}[htpb] -\begin{center} -\includegraphics[scale=0.45]{figures/badDifTreeCreate.pdf} -\caption{適切なタイミングでCommitを行わない木の復元の流れ} -\label{fig:badDifTreeCreate} -\end{center} -\end{figure} - -\begin{figure}[htpb] -\begin{center} -\includegraphics[scale=0.45]{figures/BadDifTree.pdf} -\caption{適切なタイミングでCommitを行わなかった木} -\label{fig:badDifTree} -\end{center} -\end{figure} - -\clearpage - -しかし、実際には、図\ref{fig:createGoodDifTree1}、図\ref{fig:createGoodDifTree2}のような変更が加えられる。 -以下に、適切に Commit を行った場合の木の編集の流れを記述する。 - -\begin{figure}[htpb] -\begin{center} -\includegraphics[scale=0.45]{figures/goodDifTreeCreate1.pdf} -\caption{適切なタイミングでCommitを行なう、木の復元の流れ(1回目のCommit前、Sub Tree)} -\label{fig:createGoodDifTree1} -\end{center} -\end{figure} - - -1. 木からEditorを取得し、Sub Treeのルートノードの0番目に子ノードを追加する。 - -\vspace{0.15in} -2. そして、Commitを行い、1で構築したSub Treeをメインの木にAppendする - -\begin{figure}[htpb] -\begin{center} -\includegraphics[scale=0.45]{figures/goodDifTreeCreate2.pdf} -\caption{適切なタイミングでCommitを行なう、木の復元の流れ(2回目のCommit前、Sub Tree)} -\label{fig:createGoodDifTree2} -\end{center} -\end{figure} - -3. 木からEditorを取得し、Sub Tree のルートノードの0番目に子ノードを追加する。 - -\vspace{0.15in} -4. 続いて、Sub Treeの{\tt <-1, 0>} 番目にあるノードの、0番目の子供にノードを追加する。 - -\vspace{0.15in} -5. 最後に2度目の Commit を行い、Sub Treeをメインの木にAppendする。 - -\vspace{0.15in} - -結果、図\ref{fig:goodDifTree}のような木が構築される。 - -\begin{figure}[htpb] -\begin{center} -\includegraphics[scale=0.45]{figures/goodDifTree.pdf} -\caption{適切なタイミングでCommitを行なった木の変更。} -\label{fig:goodDifTree} -\end{center} -\end{figure} - -このように、Logとして書き出されたTreeOperationから、適切な構造のDifferential Treeを復元するためには、木の構築時と同じタイミングでCommitを行う必要がある。 -そのため、Commitのタイミングを、Logとして書き出し、適切なタイミングでCommitを行えるようにした。 - - +\end{comment} \section{Differential Jungle Treeの検索} Differential Treeは、木を破壊的に編集する。 -そのため、過去の木から特定の値を持ったノードを取得する際、全てのノードを走破した場合その版の木には無いはずのノードが取得できてしまうことがある。 -そこで、その版の木が持つ末尾ノード以下のSub Treeを検索対象から除外する検索を実装した。 +そのため、過去の木に対して、Indexを使わずに全探索を行った場合、その版の木には無いはずのノードが取得できてしまう。 +そこで、その版の木が持つ末尾ノード以下のSub Treeを検索対象から除外する検索を持つ、Differential Interface Traverser を実装した。 -Indexを使用した検索を行う場合、各版に対応したIndexがあるため、Default Treeと検索の方法は変わらない。 +Indexを使用した検索を行う場合、各版に対応したIndexがあるため、Default Treeと検索のアルゴリズムは変わらない。 +これらの実装により Differential Jungle Tree は木構造の構築・検索を行う。
--- a/figures/EditDifferencialTree.graffle Mon Jan 30 03:54:57 2017 +0900 +++ b/figures/EditDifferencialTree.graffle Wed Feb 01 08:24:04 2017 +0900 @@ -53,7 +53,107 @@ <array> <dict> <key>Bounds</key> - <string>{{1034.5, 261}, {58, 46}}</string> + <string>{{124, 143.00001525878906}, {199, 118}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>YES</string> + <key>Flow</key> + <string>Resize</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>HiraKakuPro-W3</string> + <key>Size</key> + <real>24</real> + </dict> + <key>ID</key> + <integer>122</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0.974573</string> + <key>g</key> + <string>0.998064</string> + <key>r</key> + <string>1</string> + </dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Color</key> + <dict> + <key>a</key> + <string>0.75</string> + <key>b</key> + <string>0.94523</string> + <key>g</key> + <string>0.987116</string> + <key>r</key> + <string>1</string> + </dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg932\cocoartf1343\cocoasubrtf140 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuPro-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs48 \cf0 1. getJungle\ + TreeEditor()\ +}</string> + </dict> + <key>TextRelativeArea</key> + <string>{{0, 0}, {1, 1}}</string> + <key>Wrap</key> + <string>NO</string> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>ID</key> + <integer>121</integer> + <key>Points</key> + <array> + <string>{176, 247.5}</string> + <string>{331, 248.5}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>FilledArrow</string> + <key>Join</key> + <integer>0</integer> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{1033, 385.99996948242188}, {58, 46}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>FitText</key> @@ -126,7 +226,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{163.5, 249.74996948242188}, {58, 46}}</string> + <string>{{163.5, 376.99996948242188}, {58, 46}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>FitText</key> @@ -849,7 +949,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{691, 150.50003051757812}, {129, 46}}</string> + <string>{{740, 150.50003051757812}, {129, 46}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>FitText</key> @@ -913,7 +1013,7 @@ {\colortbl;\red255\green255\blue255;} \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc -\f0\fs48 \cf0 2. commit}</string> +\f0\fs48 \cf0 3. commit}</string> </dict> <key>TextRelativeArea</key> <string>{{0, 0}, {1, 1}}</string> @@ -927,8 +1027,8 @@ <integer>101</integer> <key>Points</key> <array> - <string>{678, 252}</string> - <string>{833, 253}</string> + <string>{727, 247.5}</string> + <string>{882, 248.5}</string> </array> <key>Style</key> <dict> @@ -952,8 +1052,8 @@ <integer>100</integer> <key>Points</key> <array> - <string>{603.5, 150.50003051757812}</string> - <string>{603.5, 173.99999151757834}</string> + <string>{658, 150.50003051757812}</string> + <string>{658, 173.99999151757834}</string> </array> <key>Style</key> <dict> @@ -981,7 +1081,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{563.5, 174.00001101757823}, {80, 78}}</string> + <string>{{618, 174.00001101757823}, {80, 78}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>FontInfo</key> @@ -1037,7 +1137,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{562.5, -4}, {82, 46}}</string> + <string>{{617, -4}, {82, 46}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>FitText</key> @@ -1110,7 +1210,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{563.5, 72.5}, {80, 78}}</string> + <string>{{618, 72.5}, {80, 78}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>FontInfo</key> @@ -1155,7 +1255,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{354.5, 144}, {196, 82}}</string> + <string>{{421, 140.5}, {196, 82}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>FitText</key> @@ -1219,7 +1319,7 @@ {\colortbl;\red255\green255\blue255;} \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc -\f0\fs48 \cf0 1. addNewChild\ +\f0\fs48 \cf0 2. addNewChild\ (<-1,0>)}</string> </dict> <key>TextRelativeArea</key> @@ -1234,8 +1334,8 @@ <integer>93</integer> <key>Points</key> <array> - <string>{375, 251}</string> - <string>{530, 252}</string> + <string>{441.5, 247.5}</string> + <string>{596.5, 248.5}</string> </array> <key>Style</key> <dict> @@ -1254,7 +1354,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{261.5, -4}, {82, 46}}</string> + <string>{{328, -7.5}, {82, 46}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>FitText</key> @@ -1327,7 +1427,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{262.5, 72.5}, {80, 78}}</string> + <string>{{329, 69}, {80, 78}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>FontInfo</key> @@ -1894,7 +1994,7 @@ <key>MasterSheets</key> <array/> <key>ModificationDate</key> - <string>2017-01-15 15:46:13 +0000</string> + <string>2017-01-31 08:24:47 +0000</string> <key>Modifier</key> <string>sister_clown</string> <key>NotesVisible</key> @@ -1984,7 +2084,7 @@ <key>SidebarWidth</key> <integer>120</integer> <key>VisibleRegion</key> - <string>{{-158, -4}, {1433, 787}}</string> + <string>{{-158, -13}, {1433, 787}}</string> <key>Zoom</key> <real>1</real> <key>ZoomValues</key>
--- a/indexupdate.tex Mon Jan 30 03:54:57 2017 +0900 +++ b/indexupdate.tex Wed Feb 01 08:24:04 2017 +0900 @@ -1,47 +1,41 @@ \chapter{Indexの差分Update} Jungleの木はIndexを持っており、木のCommit時に、Full Updateを行っている。 そのため、Commitを行うたび、O(n)のIndexのUpdateが入り、木の編集時大きなネックとなっていた。 -なので、Indexの差分アップデートを実装した。 +なので、高速にIndexの更新を行う差分アップデートを実装した。 \section{差分 Updateの実装} -Jungleの木に編集を行う際、編集を行ったノードをリストに格納する。 +Indexの差分 Updateを行うためには、編集を行ったノードを覚えておく必要がある。 +なので、Jungleの木に編集を行ったノードをリストに格納する。 そして、Commit時にリストにあるノードと、そのノードまでの経路にあるノードに対して、IndexをのUpdateを行う。 Indexの Update は、ノードの削除とノードの挿入の２つのプロセスで行われる。 \section{Indexの中身の削除} -IndexのUpdateを行う際、初めに木の編集後の木に存在しないノードをIndexから削除する。 +IndexのUpdateを行う際、初めに、編集後の木に存在しないノードをIndexから削除する。 削除の対象は、変更を加えたノードと、ルートから変更を加えたノードまでの経路にあるノードである。 ノードの削除は、以下の手順で行われる。 \begin{enumerate} \item 編集を行ったノードのリストからノードを取得する。 -\item 取得したノードから、保持しているデータを扱うAttributesクラスを取得する。 -\item Attributesクラスから、ノードが保持している属性名のIteratorを取得する。 -\item Attributesクラスから、3で取得した属性名とペアの属性値を取得する。 -\item 3・4で取得した属性名・属性値を使ってIndexから自身を削除する。 +\item 取得したノードが、保持している値をIndexから削除する。 \item 自身と子供のペアを ParentIndex から削除する。 \item ParentIndex から親を取得する。 -\item 2 - 7をルートノードにたどり着くか、ParentIndexから親を取得できなくなるまで続ける。 -\item 1 - 8をリストからノードが無くなるまで続ける。 +\item 2 - 4をルートノードにたどり着くか、ParentIndexから親を取得できなくなるまで続ける。 +\item 1 - 5をリストからノードが無くなるまで続ける。 \end{enumerate} \section{Indexへのノードの挿入} -Indexから不要なノードを削除した後は、木に編集を加えた際に新しく作られたノードをIndexに挿入する。 +Indexから不要なノードを削除した後は、新しく作られたノードをIndexに挿入する。 ノードの挿入は、以下の手順で行われる。 \begin{enumerate} \item 木からルートノードを取得する。 \item 取得したノードがIndexに登録されているかを調べる。 \item 登録されている場合、そのノード以下のSub Treeは、全てIndexに登録されているので、次のノードに移動する。 -\item 登録されていなかった場合、取得したノードから保持しているデータを扱うAttributesクラスと、子供を扱うChildrenクラスを取得する。 -\item Attributesクラスから、ノードが保持している属性名のIteratorを取得する。 -\item Attributesクラスから、5で取得した属性名とペアの属性値を取得する。 -\item 5・6で取得した属性名・属性値を使ってIndexに自身を登録する。 -\item 2で取得したChildrenクラスから自身の子ノードを取得する。 -\item 自身と取得した子ノードをParent Index に登録する。 -\item 全てのノードを挿入するまで 2 - 9 を繰り返す。 +\item 登録されていなかった場合、自身が保持している値をIndexに登録する +\item 自身と子ノードをParent Index に登録する。 +\item 全てのノードを挿入するまで 2 - 5 を繰り返す。 \end{enumerate}
--- a/introduciton.tex Mon Jan 30 03:54:57 2017 +0900 +++ b/introduciton.tex Wed Feb 01 08:24:04 2017 +0900 @@ -1,27 +1,30 @@ \chapter{研究目的} \pagenumbering{arabic} プログラムからデータを分離して扱うデータベースには、 -プログラム中のデータ構造とRDBの表構造のインピーダンスミスマッチという問題がある。 +プログラム中のデータ構造と Relational DataBase(RDB) の表構造のインピーダンスミスマッチという問題がある。 データベースのレコードをプログラム中のオブジェクトとして使えるOR Mapperや、 データベース自体も、表に特化したKey Value Store、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。 しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。 -そこで当研究室では、煩雑な設計を行わずプログラム内部に木構造を格納できるデータベースJungleを提案している。 +そこで当研究室では、煩雑な設計を行わず、プログラム内部に木構造を格納できるデータベースJungleを提案している。 また、Jungleは、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を取り、 木のルートをアトミックに入れ替えることでトランザクションを実現する。 プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。 Jungleは分散構成も可能である。 -Jungleは、様々の形の木構造を格納できるが、形によっては木の変更の手間が大きくなるなどの問題がある。 -そこで、本研究では、今までの汎用的な木ではなく、特定の形の木を格納することに特化させ、 -また、Index等の木の編集時にネックとなっていた箇所にも改善を行った。 +Jungleは、データの読み込みは高速に行える反面、木の変更の手間は木の形に依存しており、最悪の場合O(n)になってしまうという面があった。 +そこで、本研究では、Jungleの木の編集の高速化を行う。 +そのために、今までの汎用的な木ではなく、特定の形の木を格納することに特化した木を実装し、 +また、Indexの更新等に改善を行った。 -その後Jungleを使用した例題アプリケーションを作成し、Jungleを実際に運用した際にどのような問題が発生するかの洗い出しを行った。 +その後、実際にJungleを使用したアプリケーションを開発・運用する。 + + \section{本論文の構成} 本論文では、初めに既存のデータベースとインピータンスミスマッチについて記述する。 第 3 章では、Jungleの基本的な機能・APIについて記述する。 -第 4 章では、Indexの実装に使用する非破壊 TreeMap の実装について記述する。 +第 4 章では、改良後のIndexの実装に使用する非破壊 TreeMap の実装について記述する。 第 5 章では、Indexの差分 Update の実装について記述する。 第 6 章では、線形の木を、正順でO(1)で構築することが可能な、Differential Jungle Tree の実装について記述する。 第 7 章では、自身が Index としての機能を持つ、 Red Black Jungle Treeの実装について記述する。
--- a/jungle.tex Mon Jan 30 03:54:57 2017 +0900 +++ b/jungle.tex Wed Feb 01 08:24:04 2017 +0900 @@ -1,12 +1,12 @@ \chapter{非破壊的木構造データベースJungle} -Jungleは、当研究室が開発を行っているデータベースで、Javaを用いて実装されている。 +Jungleは、当研究室で開発を行っているデータベースで、Javaを用いて実装されている。 Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合で出来ている。 ノードは自身の子のリストと属性名と属性値の組でデータを持ち、データベースのレコードに相当する。 通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。 Jungleでは、親から子への片方向の参照しか持たない。 通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。 -この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。 +また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。 %特に非破壊木構造を採用しているJungleでは木構造の変更にo(1)からo(n)の様々な選択肢がある。つまり、アプリケーションに合わせて木を設計しない限り、 特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、 十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。 @@ -35,7 +35,7 @@ \section{非破壊的木構造} データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{fig:nondestractive})。 -その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{fig:nondestractive}の例ではノード1・3・4は編集に関係ないためノードAから参照を行い、過去の木と共有を行っている)。 +その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{fig:nondestractive}の例ではノード1・3・4は編集に関係ないため新しいルートノードから参照を行い、過去の木と共有を行っている)。 \begin{figure}[htpb] \begin{center} @@ -73,7 +73,7 @@ \section{Either} Jungleは、失敗する可能性のある関数では返り値を{ \tt Either<A、B>}に包んで返す。 -AにはのError、Bには処理に成功した際の返り値の型が入る。 +AにはError、Bには処理に成功した際の返り値の型が入る。 Eitherは、AかBどちらかの値しか持たない。 以下にEitherクラスが提供しているAPI(表\ref{EitherAPI})を記す。 \begin{table}[htb] @@ -89,14 +89,14 @@ \end{center} \end{table} -{\tt Either<A、B>}は、{\tt isA()}を用いて関数が{\tt Error}を返していないかを調べる。 +{\tt Either<A、B>} の使い方は、{\tt isA()}を用いて関数が{\tt Error}を返していないかを調べる。 {\tt Error}でない場合は{\tt b()}で関数の返り値を取得する。 \section{木の生成} -初めにJungleにおける木の生成について述べる。 +Jungleにおける木の生成について述べる。 Jungleは複数の木構造を、名前を利用して作成・編集・削除を行い管理している。 -以下にJungleクラスが提供している木の生成・管理を行うAPI(表\ref{jungleAPI})を記す。 +Jungleクラスが提供している木の生成・管理を行うAPIを表\ref{jungleAPI}に記す。 \begin{table}[htb] \begin{center} @@ -112,7 +112,8 @@ \section{JungleTree} Jungleは複数の木の集合で出来ている。 -ユーザーは、この木に対して検索や編集を行う。 +Jungleの木は、変更を加えるためのEditor・検索を行うTraversreなどを保持しており、ユーザーはそれらを用いてデータにアクセスする。 +また、過去のバージョンの木に対するアクセスや、特定のノードのPathを検索する機能も持っている。 以下にJungleTreeクラスが提供しているAPI(表\ref{JungleTreeAPI})を記す \begin{table}[htb] \begin{center} @@ -154,7 +155,7 @@ \caption{Childrenに実装されているAPI} \begin{tabular}{|p{15em}|p{24em}|} \hline {\tt int size()} & 子供の数を返す。\\ \hline - {\tt <Either Error,TreeNode> at(int num)} &ノードが持つ子供の中から、 変数{\tt num}で指定された位置にある子ノードを返す。 \\ \hline + {\tt <Either Error,TreeNode> at(int num)} &ノードが持つ子供の中から、 変数{\tt num}で指定された位置にある子ノードを返す。存在しない位置を指定した場合、{\tt Error} を返す。 \\ \hline \end{tabular} \label{Children} \end{center} @@ -166,8 +167,8 @@ \begin{center} \caption{Attributeに実装されているAPI} \begin{tabular}{|p{15em}|p{24em}|} \hline - {\tt ByteBuffer get(String key)} &ノードが持つ値から、属性名 {\tt key}とペアの属性値を{\tt ByteBuffer}型で返す。 \\ \hline - {\tt String getString(String key)} &ノードが持つ値から、属性名 {\tt key} とペアの属性値を{\tt String}型で返す。 \\ \hline + {\tt ByteBuffer get(String key)} &ノードが持つ値から、属性名 {\tt key}とペアの属性値を{\tt ByteBuffer}型で返す。ノードが保持していない{\tt key}を渡した場合エラーを返す。 \\ \hline + {\tt String getString(String key)} &ノードが持つ値から、属性名 {\tt key} とペアの属性値を{\tt String}型で返す。ノードが保持していない{\tt key}を渡した場合エラーを返す。 \\ \hline \end{tabular} \label{Attribute} \end{center} @@ -202,6 +203,7 @@ \section{木の編集API} Jungleの木の編集は{\tt Default Jungle Tree Editor}クラスを用いて行われる。 {\tt Default Jungle Tree Editor}クラスは、木に対する編集を行うAPIが定義されているJungle Tree Editorインターフェースを実装している。 +Default Jungle Tree Editorは、Jungle Tree から、{\tt getTreeEditor()}を用いて取得する。 表\ref{editor}にJungle Tree Editorインターフェースに定義されているAPIを記述する。 \begin{table}[htb] @@ -209,7 +211,7 @@ \caption{Editorに実装されているAPI} \begin{tabular}{|p{15em}|p{24em}|} \hline {\tt Either<Error, JungleTreeEditor> addNewChildAt( NodePath path, int pos)} & - 変数{\tt path}で指定した場所にあるノードの、変数{\tt pos}で指定した位置に子ノードを追加する\\ \hline + 変数{\tt path}で指定した場所にあるノードの、変数{\tt pos}で指定した位置に子ノードを追加する。\\ \hline {\tt Either<Error, JungleTreeEditor> deleteChildAt( NodePath path,int pos)} & 変数{\tt path}で指定した場所にあるノードの、変数{\tt pos}で指定した位置の子ノードを削除する。 \\ \hline {\tt Either<Error, JungleTreeEditor> putAttribute( NodePath path,String key,ByteBuffer value)} & @@ -258,10 +260,32 @@ また、木に対して行われた変更は、Logとして書き出される。 これらのAPIにより、Jungleは木構造を格納、編集する機能を持っている。 +\section{Log} +Jungle は、 Editor を用いて木に編集を加える際、使用した API に応じて対応する NodeOperation を作成する。 +NodeOperation は NodePath とペアで扱わなければならず、このペアを TreeOperation という。 +Jungle によるデータの編集は TreeOperation が複数集まった単位で commit されていく. +この TreeOperation の集まりを TreeOperationLog という。 +TreeOperationLogの仕様をソースコード\ref{src:treeoperationlog}に示す. +\begin{lstlisting}[frame=lrbt,label=src:treeoperationlog,caption=TreeOperationLogの仕様,numbers=left] +public interface TreeOperationLog extends Iterable<TreeOperation> +{ + public TreeOperationLog add(NodePath _p,NodeOperation _op); + public TreeOperationLog append(TreeOperationLog _log); + public int length(); +} +\end{lstlisting} + +\verb|Iterable<TreeOperation>|を継承しているためIteratorによりTreeOperationを取り出せるようになっている。 +addやappendメソッドを使ってTreeOperationを積み上げていくことができる。 +積み上げたLogをディスクに書き出すことで、Jungleは永続性を持つ。 +分散版Jungleでは、Logを他ノードに送ることで、データの分散を行う。 + + + \section{検索APIの実装} これまでに紹介したAPIにより、Jungleは木構造を構築できるようになった。 -しかし、木に問い合わせを行う検索APIが実装されていなかったため、属性名 {\tt key} 属性値 {\tt value}の組で検索を行うAPIの実装を、木の走査を行う{\tt Traverser}クラス内に、lambda式を用いて行った。 +しかし、木に問い合わせを行う検索APIが実装されていなかったため、木の走査を行う{\tt Traverser}クラス内に、lambda式を用いて実装した。 以下に検索を行う関数{\tt find}の定義を記述する。 \begin{lstlisting}[frame=lrbt,label=query,numbers=left] public Iterator<TreeNode> find(Query query, String key, String searchValue); @@ -295,11 +319,11 @@ \end{enumerate} -このコードの結果として、{\tt ryukyu}に所属する、名前が{\tt kanagawa}のデータが入ったノードが取得できる。 +結果として、{\tt ryukyu}に所属する、名前が{\tt kanagawa}のデータを持つノードが取得できる。 \section{Indexの実装} -Jungleには、検索の際に使用するIndexが無かったため、実装を行った。 +前節で述べた、検索の際に使用するIndexの実装を行った。 Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。 よって、全ての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要があった。 既存のTreeMapでは、一度Indexの複製を行ない、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。 @@ -351,23 +375,4 @@ JungleはこれらのAPIにより、木構造を格納、編集、検索する機能を持っている。 -\section{Log} -Jungle は、 Editor を用いて木に編集を加える際、使用した API に応じて対応する NodeOperation を作成する。 -NodeOperation は NodePath とペアで扱わなければならず、このペアを TreeOperation という。 -Jungle によるデータの編集は TreeOperation が複数集まった単位で commit されていく. -この TreeOperation の集まりを TreeOperationLog という。 -TreeOperationLogの仕様をソースコード\ref{src:treeoperationlog}に示す. -\begin{lstlisting}[frame=lrbt,label=src:treeoperationlog,caption=TreeOperationLogの仕様,numbers=left] -public interface TreeOperationLog extends Iterable<TreeOperation> -{ - public TreeOperationLog add(NodePath _p,NodeOperation _op); - public TreeOperationLog append(TreeOperationLog _log); - public int length(); -} -\end{lstlisting} - -\verb|Iterable<TreeOperation>|を継承しているためIteratorによりTreeOperationを取り出せるようになっている。 -addやappendメソッドを使ってTreeOperationを積み上げていくことができる。 - - \newpage
--- a/jungleUpdatePoint.tex Mon Jan 30 03:54:57 2017 +0900 +++ b/jungleUpdatePoint.tex Wed Feb 01 08:24:04 2017 +0900 @@ -6,7 +6,7 @@ しかし、Functional Javaは、処理が重く、実用的な性能ではなかったため、非破壊の TreeMap の実装を新しく行った。 \section{Indexの差分 Update} -Jungleの木はIndexの更新をCommit時に Full Updateで行っている。 +Jungleの木は、Indexの更新をCommit時に Full Updateで行っている。 そのため、Commitを行うたび、O(n)のIndexのUpdateが入り、木の編集時大きなネックとなっていた。 前の木との差分だけIndexを更新する機能をJungleに追加することで、この問題を解決した。 @@ -29,8 +29,9 @@ \section{Red Black Jungle Tree} Default Jungle Treeにおいて、Indexの更新は大きな手間となっている。 Indexに使用する属性名が1種類で、木構造の形がデータを表現していない場合、Jungle Tree自身をIndexとしたほうが、効率的に木構造を構築できる。 -そこで、ノードの挿入を行うと木のバランスを取る、Red Black Treeの性質を組み込んだRed Black Jungle Treeの実装を行った。 +そこで、Red Black Treeの性質を組み込んだRed Black Jungle Treeの実装を行った。 Red Black Jungle Tree は、生成時に木のバランスを取る際に使用する属性名(Balance Key)を指定する。 +ノードの挿入・削除時、Balance Keyを用いて木のバランスを取る・ Red Black Jungle Tree の木の編集は、Red Black Jungle Tree Editorを用いて行う。 ノードの挿入時に、木のバランスを取るための属性値が必要になるため、ノードと値の挿入を同時に行うAPIを実装した。
--- a/master_paper.tex Mon Jan 30 03:54:57 2017 +0900 +++ b/master_paper.tex Wed Feb 01 08:24:04 2017 +0900 @@ -77,15 +77,15 @@ %chapters \input{introduciton.tex} -\input{datebases.tex} +\input{databases.tex} \input{jungle.tex} % Jungleの説明 \input{jungleUpdatePoint.tex} % 卒論との変更点 \input{redBlackTree.tex} \input{indexupdate.tex} % Indexの差分アップデート \input{differential.tex} % 差分Treeの説明 \input{redBlackJungleTree.tex} % 赤黒木の説明 -\input{chapter4.tex} % Jungle Tree Brower -\input{chapter5.tex} % Rendering Engine +\input{jungleTreeBrowser.tex} % Jungle Tree Brower +\input{renderingEngine.tex} % Rendering Engine \input{chapter6.tex} % \input{conclusion.tex}
--- a/redBlackJungleTree.tex Mon Jan 30 03:54:57 2017 +0900 +++ b/redBlackJungleTree.tex Wed Feb 01 08:24:04 2017 +0900 @@ -1,12 +1,13 @@ \chapter{Red Black Jungle Tree} Default Jungle Treeにおいて、Indexの更新は大きな手間となっている。 Indexに使用する属性名が1種類で、木構造の形がデータを表現していない場合、Jungle Tree自身をIndexとしたほうが、効率的に木構造を変更できる。 -そこで、ノードの挿入を行うと、指定した{\tt }Keyで木のバランスを取る、Red Black Treeの性質を組み込んだRed Black Jungle Treeの実装を行った。 +そこで、Red Black Treeの性質を組み込んだRed Black Jungle Treeの実装を行った。 Red Black Jungle Tree は、木にノードの削除・追加を行った際、前述した、非破壊 Tree Map のバランスと同じアルゴリズムで木のバランスを取る。 \section{Red Black Jungle Treeの作成} Red Black Jungle Treeを作成するため、Jungleに{\tt createNewRedBlackTree(String treeName, String balanceKey)}を実装した。 これは、第一引数{\tt treeName}で受け取った名前の、第二引数{\tt balanceKey}とペアになる属性値でバランスを取るRed Black Treeを構築する。 +その際、名前が重複した場合は木の生成に失敗する。 またこれ以降の説明で使用するBalanceKeyとは、Red Black Jungle Treeを作成する時に設定したKey、BalanceValueは属性名 BalanceKeyとペアの属性値のことである。 @@ -15,19 +16,17 @@ その為、数字を使った NodePath では、編集を加える際、編集対象のノードの Path をいちいち調べる必要がある。 その問題を解決するために、NodePath を拡張した RedBlackTreeNodePath を作成し 属性名 BalanceKey 属性値 valueのペアでノードを指定できるようにした。 RedBlackTreeNodePathは、引数にString型のBalanceKeyとByteBuffer型のBalanceValueを取る。 -そして作成したPathをEditorに渡すと、指定したBalanceKeyとBalanceValueの組の値を持つノードに編集を行う。 \section{Red Black Jungle Treeの編集} -Red Black Jungle Treeへノードの追加を行う際は、追加するノードに、木のバランスを取るために必要な属性名 BalanceKeyとそのペアの属性値が必要になる。 +Red Black Jungle Treeへノードの追加を行う際は、追加するノードに、木のバランスを取るために必要な属性名 BalanceKeyとそのペアの属性値 BalanceValue が必要になる。 しかし、JungleTreeEditorには、ノードと値を同時に追加するAPIは存在しなかったため、新しく実装した。 -また、Red Black Jungle Treeにおいて、特定の属性名と属性値のペアを持つノードを削除するAPIも同時に実装した。 表\ref{NewEditorAPI}に新しく実装したAPIを記述する。 \begin{table}[htb] \begin{center} \caption{新たにJungle Tree Editorに定義したAPI} -\begin{tabular}{|p{15em}|p{24em}|} \hline +\begin{tabular}{|p{16em}|p{24em}|} \hline {\tt Either<Error, JungleTreeEditor> addNewChildAndPutAttribute( NodePath path, int pos, String key, ByteBuffer value)} & pathで指定した位置にあるノードのpos番目に、属性名 keyと属性値 valueの組を持つノードを追加する。\\ \hline \end{tabular} \label{NewEditorAPI} @@ -42,10 +41,10 @@ \begin{table}[htb] \begin{center} \caption{Red Black Jungle TreeとDefault Jungle TreeのAPIの違い} -\begin{tabular}{|p{15em}|p{24em}|} \hline +\begin{tabular}{|p{16em}|p{24em}|} \hline {\tt Either<Error, JungleTreeEditor> addNewChildAt(NodePath path, int pos)} & pathとposは使用せず、属性名 balanceKey 属性値 "Default Value"を持ったノードを、Red Black Treeの挿入アルゴリズムに則って挿入し、バランスを取る。 \\ \hline -{\tt Either<Error, JungleTreeEditor> addNewChildAndPutAttribute(NodePath path, int pos, String key, ByteBuffer value)} & pathとposは使用せず、属性名 key 属性値 valueを持ったノードを、Red Black Treeの挿入アルゴリズムに則って挿入し、バランスを取る。 第二引数にBalanceKey以外の値を渡した場合、バランスが取れない為、ノードの挿入は失敗する。\\ \hline -{\tt Either<Error, JungleTreeEditor> replaceNewRootNode()} & 赤黒木は、新しくルートを追加する意味が無いので使用しない。実行した場合エラーを返す。\\ \hline +{\tt Either<Error, JungleTreeEditor> addNewChildAndPutAttribute (NodePath path, int pos, String key, ByteBuffer value)} & pathとposは使用せず、属性名 key 属性値 valueを持ったノードを、Red Black Treeの挿入アルゴリズムに則って挿入し、バランスを取る。 第二引数にBalanceKey以外の値を渡した場合、バランスが取れない為、ノードの挿入は失敗する。\\ \hline +{\tt Either<Error, JungleTreeEditor> replaceNewRootNode()} & 赤黒木では使用しない。実行した場合エラーを返す。\\ \hline {\tt Either<Error, JungleTreeEditor> moveChild(NodePath path, int childNum, String move)} & ノードを動かすと木のバランスが崩れるため使用しない。実行した場合エラーを返す。 \\ \hline \end{tabular} \label{EditorDifference} @@ -77,7 +76,7 @@ ソースコード\ref{src:rbtEdit}の解説を以下に記す。 \begin{enumerate} \item 木のバランスに使用するbalanceKeyを宣言する。 -\item 1で宣言したbalanceKeyを使って、Red Black Jungle Treeを{\tt TreeName}とい名前で作成する。 +\item 1で宣言したbalanceKeyを使って、Red Black Jungle Treeを{\tt TreeName}という名前で作成する。 \item 2で作成した木からEditorを取得する。 \item 木の編集に使用するPathを作成する。 \item 木にノードを値を挿入する際、属性名 balanceKeyとペアになる属性値 balanceValueを作成する。 @@ -93,13 +92,21 @@ \item 編集を木にCommitする。 \end{enumerate} +Red Black Jungle Tree は、木の編集時 Index を更新しないので、Default Jungle Tree より高速に木の変更を行える。 + \section{Jungle Red Black Treeの検索} -Red Black Jungle Treeへの検索は、Red Black Jungle Tree Traverserを用いて行う。 -Red Black Jungle Treeは、Indexを持たないため、Traverser.find(Query query, String balanceKey, String balanceValue)の第二・第三引数は、木を作成する時に設定したbalanceKey・属性名 balanceKeyとペアのbalanceValueを取る。 -初めに、balanceKeyとbalanceValueを使って、二分探索木の探索アルゴリズムを用いて条件に一致するノードを絞り込む。 -そして、絞り込んだノードが、Queryの条件と一致した場合、そのノードを返す。 -また、balanceKey以外の値を第二引数に渡した場合、検索は失敗する。 +Red Black Jungle Treeへの検索は、Red Black Jungle Tree Interface Traverser が提供しているAPIを用いて行う(表\ref{RedBlackTreeInterfaceTraverserApi})。 -balanceKey・balanceValueを引数に取らないTraverser.find(Query query)を使用する場合、Default Jungle TreeのIndexを使わない検索と同じで、木の全探索を行う。 -その際の探索オーダーはO(n)となる。 +\begin{table}[htb] +\begin{center} +\caption{Red Black Jungle Tree Interface Traverser が提供しているAPI} +\begin{tabular}{|p{16em}|p{24em}|} \hline +{\tt Iterator<TreeNode> find(Query query, String Balancekey, String BalanceValue)} & 第二引数と第三引数で指定した値を持ち、Queryの条件と一致するノードを返す。BalanceKey と BalanceValue を用いて木の二分探索を行うので、探索オーダーはO(Log n)である。また第二引数に、木の生成時指定した、Balance Key 以外を渡した場合、探索は失敗する。\\ \hline +{\tt Iterator<TreeNode> find(Query query)} & Query の条件と一致するノードを、木の全探索で検索する。探索オーダーはO(n)である。\\ \hline +\end{tabular} +\label{RedBlackTreeInterfaceTraverserApi} +\end{center} +\end{table} + +Red Black Jungle Tree は、これらの実装により、木構造の構築・検索を行える。
--- a/redBlackTree.tex Mon Jan 30 03:54:57 2017 +0900 +++ b/redBlackTree.tex Wed Feb 01 08:24:04 2017 +0900 @@ -1,5 +1,5 @@ \chapter{非破壊 TreeMap の実装} -JungleのIndexでは、Functional Javaの非破壊 TreeMap を用いて実装を行っていた。 +JungleのIndexは、Functional Javaの非破壊 TreeMap を用いて実装を行っている。 しかし、Functional Java の TreeMap は、木の変更の手間が大きい、並列実行時処理速度が落ちるなど、実用的な性能を持っていなかった。 なので、Jungleで使用するための非破壊 TreeMap を作成した。 TreeMapは、Red Black Treeのアルゴリズムに基づき実装した。 @@ -22,29 +22,32 @@ 非破壊 TreeMapは、Javaのジェネリクスを用いて、{\tt TreeMap<K,V>Key}と定義されており、 TreeMapを作る際に、K,Vに任意の型を記述することで、 KeyとValueで使用する型を設定できる。 +ソースコード\ref{src:TreeMapExample}に、 Key を String 型・ Value を ByteBuffer 型で定義するサンプルコードを記述する。 -ソースコード\ref{createTreeMap}に、KeyをString型・Value を ByteBuffer 型 で宣言する例を記述する。 +\begin{lstlisting}[frame=lrbt,numbers=left,label=src:TreeMapExample,caption=TreeMapの定義サンプル] +TreeMap<String, ByteBuffer> map = new TreeMap<>(); +\end{lstlisting} - +\newpage \section{非破壊 TreeMap のAPI} -非破壊 TreeMap は、表\ref{RedBlackTreeAPI}に記述してあるAPIを提供している。 +非破壊 TreeMap は、値の挿入・削除を行うために、表\ref{RedBlackTreeAPI}に記述してあるAPIを提供している。 \begin{table}[htb] \begin{center} \caption{非破壊 TreeMap に実装されているAPI} \begin{tabular}{|p{15em}|p{24em}|} \hline {\tt Node getRoot()} & TreeMap のルートノードを返す。 \\ \hline -{\tt boolean isEmpty()} & TreeMap に値が入っているなら{\tt true}を返す。 \\ \hline +{\tt boolean isEmpty()} & TreeMap が値を保持していないなら{\tt true}を返す。 \\ \hline {\tt TreeMap<K,V> put(K key, V value)} & TreeMap に{\tt key:value} の組で値を挿入し、新しい TreeMap を返す。 \\ \hline {\tt TreeMap<K,V> delete(K key)} & TreeMap に{\tt key} とペアで格納されている値を削除し、新しい TreeMap を返す。\\ \hline -{\tt Iterator<K> keys()} & TreeMap が持っている全ての {\tt key} を Iteratorで返す。 \\ \hline +{\tt Iterator<K> keys()} & TreeMap が保持している全ての {\tt key} を Iteratorで返す。 \\ \hline \end{tabular} \label{RedBlackTreeAPI} \end{center} \end{table} -非破壊 TreeMapは、通常の TreeMap と異なり、put・deleteを行うと編集後の新しい TreeMap を返すため、新しい TreeMap で受ける必要がある。 +非破壊 TreeMapは、put・deleteを行うと編集後の新しい TreeMap を返すため、新しい TreeMap で受ける必要がある。 この時返ってくるTreeMapと、編集前のTreeMapは別オブジェクトである。 \section{非破壊 Red Black Treeへのデータの挿入} @@ -59,6 +62,7 @@ \end{enumerate} Red Black Treeのデータ挿入時のバランスは、次の5パターンに分けられる。 +これ以降の説明では、挿入したノードは、ノードinsと記述する。 \section{データ挿入時のバランス ケース1} @@ -101,7 +105,8 @@ \end{center} \end{figure} -バランス後、ノードAを新しくノードinsとして再帰的に木のバランスを行う。 + +バランス後、ノードAの色が変わってしまったため、ノードAを新しくノードinsとして再帰的に木のバランスを行う。 この変更は最悪の場合ルートまで続く。 \section{データ挿入時のバランス ケース4} @@ -112,8 +117,8 @@ \item ノードinsがノードBの木の中心側の子。 \end{enumerate} -バランス時、上記の条件を満たしている場合、ノードBを中心に外側に回転処理を行い(\ref{fig:RedBlackTreeInsert3})、次節に記述するバランス5を行う。 -その際、ノードBをinsとして扱う。 +バランス時、上記の条件を満たしている場合、ノードBを中心に外側に回転処理を行い(図\ref{fig:RedBlackTreeInsert3})、次節に記述するバランス5を行う。 +その際、ノードBをノードinsとして扱う。 \begin{figure}[htpb] \begin{center} @@ -151,12 +156,12 @@ \begin{enumerate} \item 削除を行うノードと、現在のノードを比較する。 -\item 比較の結果、大きかった場合右に、小さかった場合左のノードに進む。 +\item 比較の結果、大きかった場合右、小さかった場合左のノードに進む。 \item 削除を行うノードにたどり着くまで、１・２を繰り返す。 \item ノードに子が無い場合削除を行う。 \item 片側に部分木(子ノード)がある場合、ノードを削除した後、部分木のルートを昇格させる。 \item 両側に部分木(子ノード)がある場合は、左部分木の最大の値を持つノードの値を取得し、削除を行うノードと同じ色に変更した後、置換する。 -\item 置換したノードを削除する(ここで削除させるノードは部分木の最大値であるため、子ノードは1つ以下、つまり削除の手順2・3どちらかの手順で削除できる)。 +\item 置換したノードを削除する(ここで削除させるノードは部分木の最大値であるため、子ノードは1つ以下、つまり削除の手順4・5どちらかの手順で削除できる)。 \item 削除したノードから、木のバランスを取りながら、ルートまでの経路の複製を行う。その際Defaul Jungle Treeと同じように、変更が加えられないノードへは参照を行い過去の木と最大限共有を行う。 \end{enumerate} @@ -218,7 +223,7 @@ \item ノードAが赤。 \end{enumerate} -上記の条件を満たしている場合、ノードAを黒に、ノードBを赤に変更する。 +上記の条件を満たしている場合、ノードAを黒に、ノードBを赤に変更する(図\ref{fig:RedBlackTreeDelete3})。 そうすることで、ノードA側の右側のSub Treeの黒の深さを変えることなく、左側のSub Treeの黒の深さが1つ増え、バランスが取れる。 \begin{figure}[htpb] \begin{center} @@ -236,7 +241,7 @@ \item ノードEの色が赤。 \end{enumerate} -上記の条件を満たしている場合、ノードBを中心に外側に回転、その後、ノードEを黒に、ノードBを赤に変更する。 +上記の条件を満たしている場合、ノードBを中心に外側に回転、その後、ノードEを黒に、ノードBを赤に変更する(図\ref{fig:RedBlackTreeDelete4})。 そして、データ削除時のバランス ケース7に帰着する。 \begin{figure}[htpb] @@ -255,7 +260,7 @@ \item ノードFの色が赤。 \end{enumerate} -上記の条件を満たしている場合、ノードAを中心にノードrep側に回転、その後、ノードAとノードBの色を交換し、ノードFを黒にする。 +上記の条件を満たしている場合、ノードAを中心にノードrep側に回転、その後、ノードAとノードBの色を交換し、ノードFを黒にする(図\ref{fig:RedBlackTreeDelete5})。 そうすることで、ノードE・Fの黒の深さを変えること無く、ノードrepの黒の深さを1増やせるため、木のバランスが取れる。 \begin{figure}[htpb]