#appengine で skiplist ってすごくね?・その2

@koher それは思いました。skiplistとb-treeの違いがいまいちよく分かってません＞＜

2010-04-26 00:57:40

Skiplistと違ってB-treeだとlogM(N)にできます。底を1000くらいにすれば、2、3回のデータストアアクセスで10万単位のランキングを作れるんじゃないかと。問題は、数KB程度のエンティティの読み書きがどの程度の速度で行えるかです。 #appengine #ajn7

2010-04-26 01:00:13

@kazunori_279 B-treeだと1000分木でも作れるので、Datastoreへのアクセス回数が極端に少なくなります。ただし、エンティティのサイズは大きくなるので、データサイズ増大の負荷 < 多数回アクセスの負荷であれば高速化できるかと思います。

2010-04-26 01:02:30

実装してないので確証はないですが、原理的にはSkiplistと同じようにB-treeもIndexableにできるように思います。残念なのは、今週は仕事で時間をとれなさそうなことです…。時間が取れ次第ライブラリとして実装して公開したいと思います。 #appengine #ajn7

2010-04-26 01:05:50

.@koher いいですねそれ! なんか俺様DB実装みたい...既存DBのB-Treeと異なるのは、個々のentityが分散化して保存されることかな。。

2010-04-26 01:10:30

これはskip listも同じです。RT @koher: Skiplistと違ってB-treeだとlogM(N)にできます。 #appengine

2010-04-26 01:13:54

はい、そう思います。RT @koher: 実装してないので確証はないですが、原理的にはSkiplistと同じようにB-treeもIndexableにできるように思います。残念なのは、 #appengine #ajn7

2010-04-26 01:21:13

Skip ListとB-treeのような既存の木構造の検索能力にそう違いはありません。Skip Listは、logM(N) のMは2ですが大きくすることは可能です。本質的な違いはSkip Listが乱数を使って上位のリンク構造を決めている点.で、これが分散化に寄与します。

2010-04-26 01:28:49

Skip Listの利点はバランスさせるための処理が不要である点です。既存のバランス木はバランスさせるための処理が必要で、このためアルゴリズムが複雑になります。このため、バランス木の各ノードを異なるマシンに分散化させることが困難になります。

2010-04-26 01:33:52

構造化オーバーレイは、木構造を使った探索アルゴリズムをP2Pネットワークに広げた方式と見ることができます。DHTの場合は、ID空間に一様にノードが分布するという前提があり、通常のN分木探索をそのまま適用することができました。

2010-04-26 01:38:15

それは、DHTにはノードが一様に分布するという前提があるため、N分木を構成する際にバランスのための処理がはぶけるためです。

2010-04-26 01:40:10

.@kibayos Datastore上の実装を考えると、SkiplistでMを増やしても各階層でたどるノードが増えて結局M=2のときと同程度のアクセス回数になりませんか？B-treeだと一つのエンティティにM個のポインタをまとめられます。 #appengine #ajn7

2010-04-26 01:41:16

@kibayos @koher #appengine という既存の分散データストア上にアプリレベルで実装する場合、個々のエンティティのバランスは気にしなくてよいのですよね。。そもそもアプリレベルっていうのが既存skipgraphと違う点の気がします

2010-04-26 01:41:33

ところが、構造化オーバーレイにおいて、任意のkeyをノードに割り当て、範囲探索を行うとすると、ノードの持つkeyが一様に分布するという前提は成り立ちません。ここにおいて、バランスの不要なSkip Listが意味を持つのです。

2010-04-26 01:43:17

.@kibayos Skiplistも工夫すれば一つのエンティティに同階層の複数ノードへのポインタをまとめられるかもしれませんが、縦のつながりもあるので実装がややこしそうに感じます。 #appengine #ajn7

2010-04-26 01:43:34

こうしたSkip Listの持つ特性を生かして生まれたのがSkip Graphです。DHTにはたくさんの方式が有るのに対し、範囲検索に向く構造化オーバーレイはSkip Graphしかないのは、バランス処理がいらないバランス木がSkip Listしかないためです。

2010-04-26 01:46:18

@kazunori_279 おっしゃるように #appengine 上での実装では分散は特に気にしなくてもよいと思います。あと、Skiplistでも挿入時にlog N個のノードを書き換えているので、B-treeのバランスさせる処理が特に大きな負荷にはならないと考えています。

2010-04-26 01:50:40

B-treeとそう違いないのでは。RT @koher: .@kibayos Skiplistも工夫すれば一つのエンティティに同階層の複数ノードへのポインタをまとめられるかもしれませんが、縦のつながりもあるので実装がややこしそうに感じます。 #appengine #ajn7

2010-04-26 01:51:19

いえいえ、B-treeを批判しているつもりはなくて、@kazunori_279 さんの言うよう、現前提ではどっちでもよいと思っています。一連の自分のTLを見てもらえば解りますが、両者の違いを知ってほしいのです。 #appengine

2010-04-26 01:54:28

.@kazunori_279 @kibayos 素晴らしいのは、Datastore上での実装ではB-treeの、最大でストレージの半分を無駄にしてしまうという欠点がなくなることです。単純なB-treeなら実装の複雑さもSkiplistと大して変わりません。 #appengine

2010-04-26 01:57:30

@kibayos @koher ではB-TreeでもOKと仮定すると、既存DBのインデックスとの違いは何でしょう。レコードが分散化されている点かな？何10億レコードあってもさくっと平均とれたりするのってすごいと思うのだけど。。

2010-04-26 01:58:02

RT @kumagi: ブログ書いた。みんな大好きLockfreeListについて http://d.hatena.ne.jp/kumagi/20100425 ハザードポインタの次のlockfree資料はHashsetかSkiplistのどちらに需要があるのかしら？

2010-04-26 01:59:35