# HG changeset patch
# User tatsuki
# Date 1486893336 -32400
# Node ID 92d6882c114390cdb4ae8e45c3b56db5ee0ba4f0
# Parent 222d98af3372e177e81b2de559283c39cf5a12c6
add svg
diff -r 222d98af3372 -r 92d6882c1143 slide/images/EditDifferencialTree.svg
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slide/images/EditDifferencialTree.svg Sun Feb 12 18:55:36 2017 +0900
@@ -0,0 +1,610 @@
+
+
\ No newline at end of file
diff -r 222d98af3372 -r 92d6882c1143 slide/images/PushPopDemerit.svg
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slide/images/PushPopDemerit.svg Sun Feb 12 18:55:36 2017 +0900
@@ -0,0 +1,305 @@
+
+
\ No newline at end of file
diff -r 222d98af3372 -r 92d6882c1143 slide/images/comparedb.svg
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slide/images/comparedb.svg Sun Feb 12 18:55:36 2017 +0900
@@ -0,0 +1,262 @@
+
+
\ No newline at end of file
diff -r 222d98af3372 -r 92d6882c1143 slide/images/createIndex.svg
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slide/images/createIndex.svg Sun Feb 12 18:55:36 2017 +0900
@@ -0,0 +1,275 @@
+
+
\ No newline at end of file
diff -r 222d98af3372 -r 92d6882c1143 slide/images/createListTree.svg
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slide/images/createListTree.svg Sun Feb 12 18:55:36 2017 +0900
@@ -0,0 +1,275 @@
+
+
\ No newline at end of file
diff -r 222d98af3372 -r 92d6882c1143 slide/images/createRedBlackTreeAndDefaultTreeTime.svg
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slide/images/createRedBlackTreeAndDefaultTreeTime.svg Sun Feb 12 18:55:36 2017 +0900
@@ -0,0 +1,212 @@
+
+
\ No newline at end of file
diff -r 222d98af3372 -r 92d6882c1143 slide/images/find.svg
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slide/images/find.svg Sun Feb 12 18:55:36 2017 +0900
@@ -0,0 +1,222 @@
+
+
\ No newline at end of file
diff -r 222d98af3372 -r 92d6882c1143 slide/images/findDifTree.svg
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slide/images/findDifTree.svg Sun Feb 12 18:55:36 2017 +0900
@@ -0,0 +1,426 @@
+
+
\ No newline at end of file
diff -r 222d98af3372 -r 92d6882c1143 slide/images/findTime.svg
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slide/images/findTime.svg Sun Feb 12 18:55:36 2017 +0900
@@ -0,0 +1,242 @@
+
+
\ No newline at end of file
diff -r 222d98af3372 -r 92d6882c1143 slide/images/multiComponent.svg
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slide/images/multiComponent.svg Sun Feb 12 18:55:36 2017 +0900
@@ -0,0 +1,217 @@
+
+
\ No newline at end of file
diff -r 222d98af3372 -r 92d6882c1143 slide/images/nodepath.svg
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slide/images/nodepath.svg Sun Feb 12 18:55:36 2017 +0900
@@ -0,0 +1,371 @@
+
+
\ No newline at end of file
diff -r 222d98af3372 -r 92d6882c1143 slide/images/non_destructive_tree.svg
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slide/images/non_destructive_tree.svg Sun Feb 12 18:55:36 2017 +0900
@@ -0,0 +1,795 @@
+
+
\ No newline at end of file
diff -r 222d98af3372 -r 92d6882c1143 slide/slide.html
--- a/slide/slide.html Sun Feb 12 18:09:55 2017 +0900
+++ b/slide/slide.html Sun Feb 12 18:55:36 2017 +0900
@@ -125,9 +125,11 @@
データベースのトランザクションとデータ構造のギャップ
+
データベースには、複数のレコードをアップデートするときに、整合性を維持する仕組みとしてトランザクションがある。
データ構造には並行処理ようにスレッドセーフなものが用意されている。しかし、複数のスレッドセーフなデータ構造はアクセスするときに整合性を維持するトランザクションは自分で用意する必要があり、標準的なものは用意されていない。
特に複数のリストや木構造に対してトランザクションが必要になってきている。
+
@@ -168,10 +170,12 @@
Jungleはゲームなどのアイテムのリストをそのまま木構造に格納することができ、トランザクションと持続性を提供する。
Jungleは様々な構造のデータ(例えばXML/JSON/LIST)を木構造としてそのまま格納することが可能である。
決まった版の木は変更されないので、いちいち木を検索することなく木構造をそのままプログラムのデータ構造として用いることができる。
-
+
+
Jungleの構造とAPI
+
以下では、Jungleの構成要素と木へのアクセス方法を説明する。
- 木とノード
@@ -180,23 +184,28 @@
- NodePath
- ノードの編集
- 検索機能
+
+
+
@@ -226,8 +235,8 @@
Jungleでは木のノードの位置をNodePathを使って表す。
ルートから対象のノードまでの経路を数字で指し示す。
ルートノードは例外として-1と表記される。
-NodePathクラスを用いて[-1,1,2,3]を表している例を以下に貼る。
-
+NodePathクラスを用いて[-1,1,2,3]を表している例を以下に記述する。
+
@@ -247,23 +256,6 @@
-
-
-
-
JungleTreeEditorのAPI
-
-JungleTreeEditorが提供している木の編集APIを以下に記す。
-
-
-
-
Jungleの検索機能
@@ -290,11 +282,12 @@
本修論でのJungleの改良点
-- 高速な非破壊赤黒木の実装(O(log n))
-
- 検索APIの実装(卒論時)
-
- Indexの差分アップデート(O(log n))
-
- 線形リストの高速化(O(1))
-
- Jungle Tree自体のバランス化による大きな木の扱い(O(log n))
+
- 高速な非破壊赤黒木の実装(O(log n))
+- 検索APIの実装(卒論時)
+- Indexの差分アップデート(O(log n))
+- 線形リストの高速化(O(1))
+- Jungle Tree自体のバランス化による大きな木の扱い(O(log n))
+
@@ -347,50 +340,51 @@
逆にルートを取り除き、その子供をルートにする操作(Pop)もO(1)である。
これらにより、線形木を高速に操作することができる。
Pushを連続で行うと、リストは逆順に構築される。
-
+
-
-Differential Jungle Treeの作成API
-Differential Jungle Treeは、特別なAPIで作成する必要がある。
+
+差分木の作成API
+差分木は、特別なAPIで作成する必要がある。
JungleTree createNewDifferenceTree(String treeName);
-差分木への追加を複数回行うと、複数回のトランザクション処理を行う必要がある。
-複数の追加をSub Treeに対して破壊的に行って、そのSub Treeを差分木へ追加することにより、トランザクションを一回で済ませることができるようにしている。
+差分木への追加を複数回行うと、複数回のトランザクション処理を行う必要がある。
+
+複数の追加をSub Treeに対して破壊的に行って、そのSub Treeを差分木へ追加することにより、トランザクションを一回で済ませることができるようにしている。
-
+
Differential Jungle Treeの整合性
Default Jungle TreeへCommitは編集後の木のルートをAtomicに入れ替えることで行う。
しかしDifferential Jungle Treeは、ルートの入れ替えと、Editorが持つ木構造の末尾ノードへのAppendの２つのプロセスからなる。
@@ -402,7 +396,7 @@
-
+
Jungle上での巨大な木の扱い
Jungleは木の編集時、ルートから編集を行う位置までのノードの複製を行う。
そのため、木の編集の手間は木構造の大きさにも依存している。
@@ -414,7 +408,7 @@
-
+
Red Black Jungle Treeの作成API
Red Black Jungle Treeは、特別なAPIで作成する必要がある。
@@ -428,7 +422,7 @@
-
+
NodePathの拡張
Red Black Jungle Treeは、ノードを追加、削除するたびに木のバランスが行われるため、各ノードのPathが変わってしまう。
その為、編集を加える際に、編集対象のノードのPathを調べる必要がある。
@@ -439,21 +433,23 @@
-
+
新たに追加した要素の評価
-Jungleに新しく追加した機能の性能測定を行う。
-新しく実装したTreeMapとFunctionalJavaのTreeMap
-IndexのFullアップデートと差分アップデート
-Default Jungle TreeとDefferential Jungle Tree
-Default Jungle Tree と Red Black Jungle Tree
-最後に既存のDBであるPostgreSQLとMongoDBとJungleの比較を行う。
+
+- Jungleに新しく追加した機能の性能測定を行う。
+- 新しく実装したTreeMapとFunctionalJavaのTreeMap
+- IndexのFullアップデートと差分アップデート
+- Default Jungle TreeとDefferential Jungle Tree
+- Default Jungle Tree と Red Black Jungle Tree
+- 最後に既存のDBであるPostgreSQLとMongoDBとJungleの比較を行う。
+
-
+
TreeMapの測定の考察
新たに実装したTreeMapの方が極めて高速な検索を行えている。
理由として、JungleのTreeMapは二分探索木の探索アルゴリズムで探索するのに対して、Functional Javaは検索対象のノードがルートになる木を再構築し、ルートを返すといったアルゴリズムのを採用しているからである
@@ -477,7 +473,7 @@
-
+
Indexの差分アップデートの測定の考察
IndexのFullアップデートに比べて差分Updateの方が高速に木の構築に成功している。
期待通りの性能が出たといえる。
@@ -498,7 +494,7 @@
-
+
正順の線形木の構築時間の考察
Commit毎に全てのノードの複製を行うDefault Jungle Treeに比べて、木の複製を行わないDifferential Jungle Treeが早いのは当然だといえる。
期待通りの性能が出た。
@@ -520,35 +516,34 @@
-
+
Red Black Jungle Tree の測定の考察
Red Black Jungle Treeは自身の木の形がIndexと同じ働きを持っている。
-なのでIndexを木の編集時作る必要がない。
Commit のたびにIndexを作っているDefault Jungle Treeより早くなるのは当然だといえる。
期待通りの性能が出た。
-
+
既存のDBとJungleの比較の考察
MongoDBとPostgreSQLは、プログラム外にあるデータベースに通信を用いてアクセスしている。
Jungleは、メモリの中にデータを持ち通信を使わずデータにアクセスできる。
@@ -559,14 +554,15 @@
-
+
まとめ
Jungleの性能を向上させるために新たな要素を追加した。
-- 非破壊TreeMap
-- Indexの差分アップデート
-- Differential Jungle Tree
-- Red Black Jungle Tree
+- 高速な非破壊赤黒木の実装(O(log n))
+- 検索APIの実装(卒論時)
+- Indexの差分アップデート(O(log n))
+- 線形リストの高速化(O(1))
+- Jungle Tree自体のバランス化による大きな木の扱い(O(log n))
実装後の測定では、全てが既存の木と比べて高速に動いていた。
また、Jungleは既存のDBと比較しても、極めて高速な検索が行えることがわかった。
@@ -575,7 +571,7 @@
-
+
今後の課題
木の設計手法の確立
JungleはRDB と異なり格納するデータの自由度は大きい。
@@ -586,6 +582,16 @@
+
+発表履歴
+
+- 非破壊的木構造データベースJungleとその評価, 金川竜己 , 河野真治 (琉球大学)
システムソフトウェアとオペレーティング・システム研究会 ,2015 Okinawa, May, 2015
+- ソフトウェア内部で使用するのに適した木構造データベースJungle
金川竜己, 武田和馬(琉球大学), 河野真治(琉球大学),第58回プログラミング・シンポジウム, Jan, 2017
+
+
+