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

koher @koher

.@kibayos 確かに、横（同階層）を一つのエンティティにおさめて、縦を別のエンティティに分離するとできそうですね。B-treeとどちらで実装した方が簡単か検討してみます。ありがとうございます。

Kazunori Sato @kazunori_279

@kibayos lock freeは重要ですね

koher @koher

.@kazunori_279 @kibayos 既存のDBのインデックスでも、合計値や要素番号の情報を負荷すれば平均・合計・中央値を即座に取得できると思いますよ。むしろなぜそれが既存のDBに実装されてないのか不思議ですね。そうすればCOUNTがあれほど遅いこともなくなりますし。

Kazunori Sato @kazunori_279

まさしくその疑問です RT @koher: 既存のDBのインデックスでも、合計値や要素番号の情報を負荷すれば平均・合計・中央値を即座に取得できると思いますよ。むしろなぜそれが既存のDBに実装されてないのか不思議ですね。そうすればCOUNTがあれほど遅いこともなくなりますし。

Mikio Yoshida @kibayos

B-treeのリンクにIndexable Skiplistのような情報の付与をするという発想が生まれなかったためと思います。RT @kazunori_279: まさしくその疑問です RT @koher: 既存のDBのインデックスでも、合計値や要素番号の情報を負荷すれば平均・合計

koher @koher

同時更新はロックが必要だと思っていたのですがロック不要ですか？資料があれば教えていただけるとうれしいです。元の論文を当たればよいでしょうか？ QT @kibayos: Skip Listと既存のバランス木の違いで、lock freeにできるかも大事な点でした。

Mikio Yoshida @kibayos

既存の集中システムではメモリは大事だったし。RT @kibayos: B-treeのリンクにIndexable Skiplistのような情報の付与をするという発想が生まれなかったためと思います。RT @kazunori_279: まさしくその疑問です RT @koher:

koher @koher

.@kazunori_279 不思議ですね〜。まさか誰もB-treeをIndexableにできる可能性に気付かなかったとは思えないですし。

Kazunori Sato @kazunori_279

そこが転換点なのですね.. RT @kibayos: B-treeのリンクにIndexable Skiplistのような情報の付与をするという発想が生まれなかったためと思います。RT @kazunori_279: まさしくその疑問です RT @koher: 既存のDB...

Mikio Yoshida @kibayos

不要です。Java6のConcurrentSkipListMapのJavaDocとかいかが。RT @koher: 同時更新はロックが必要だと思っていたのですがロック不要ですか？資料があれば教えていただけるとうれしいです。

Kazunori Sato @kazunori_279

@koher これまでは何でもメモリ上でadhocに処理できたから、特定クエリに合わせてあらかじめリンクに値を載せておく何て必要性がなかったのかもしれませんね。

koher @koher

え、ではもしかしてすごいことに気づいてしまったのでしょうか…。 QT @kazunori_279: そこが転換点なのですね.. RT @kibayos: B-treeのリンクにIndexable Skiplistのような情報の付与をするという発想が生まれなかったためと思います。

Mikio Yoshida @kibayos

RT @shudo: 2010/4/24の勉強会・議論で紹介した "Modular Data Storage with Anvil" http://bit.ly/c18Tm (Anvilのウェブページ) (Thanks SOSP 2009報告会, 2009/11/5)

koher @koher

ありがとうございます！見てみます。Java6でそんなクラスが追加されていたんですね。 QT @kibayos: 不要です。Java6のConcurrentSkipListMapのJavaDocとかいかが。

Kazunori Sato @kazunori_279

@koher いずれにせよ #appengine 上ではすごく重要なパターンになると思いますね＞エンティティ間のリンクに値を持たせて集計

Kazunori Sato @kazunori_279

RT @kumagi: 平衡2分木はLock-freeな物が実在する、と以前言った気がしますが、今のところCASベースの物が無くSTMベースな物だけで、STM故に衝突時のパフォーマンス低下が著しいです。なのでSkipListが日の目を見る珍しい世界になってます。

koher @koher

.@kazunori_279 本当ですね！集計関数も含めて実装してみます。わくわくしてきました。 #appengine > いずれにせよ #appengine 上ではすごく重要なパターンになると思いますね

Kazunori Sato @kazunori_279

RT @satoruf: BI系のAnalytic DBは持っている物が多いようです QT @kazunori_279 まさしくその疑問です RT @koher: 既存のDBのインデックスでも、合計値や要素番号の情報を負荷すれば平均・合計・中央値を即座に取得できると思います..