[B! algorithm] ita-wasaのブックマーク

ita-wasa id:ita-wasa

algorithmに関するita-wasaのブックマーク (3)

DO++: 左傾赤黒木
漢字で書くと仰々しいが、赤黒木 (wikipedia) red-black tree (english wikipedia)という平衡二分木で最も多くつかわれているデータ構造の、改善版が出てたそうだ。 left-leaning red-black tree (pdf) 日本語に訳すと左傾赤黒木かな。簡単な漢字を並べている感じがしてしまう赤黒木の詳細については、wikipediaなどをよんでもらうとして、これは更新時間が定数で更新箇所が局所的（これはマルチスレッドとかでロックする箇所をかなり細かい単位で、できるという強い利点もある）のだが、実装が結構面倒くさい。例えばC++ stl のmapとかの赤黒木の実装のstl_tree.h(google code search)は大変なことになっている（特にRb_tree_rebalance_for_eraseとか）赤黒木というのは動的データ構造
ita-wasa 2008/11/10
で、このleft-leaning red-black treeだと、赤黒木の実装がすごいシンプルになって、挿入で３０行強、削除で８０行ぐらいで書ける。なぜシンプルになったかというと、今までの赤黒木は対応する2-3-4木が必ずあるといっても3-node

algorithm
リンク
Part2　トランザクションの障害回復
企業のアプリケーションでは，どんな傷害が起こってもトランザクションのACID特性が保証される仕組みが必要になります。では，2フェーズコミットを実装している分散トランザクション環境において，障害発生時にトランザクションのACIDはどのように保障されるのでしょうか？Part2では，DTPモデルに準拠した一般的な分散トランザクション処理における，トランザクションのリカバリーについて説明しましょう。企業のアプリケーションでは，あらゆる障害に対して，データの保全と整合性を保証する仕組みが必要です。トランザクション処理中に，サーバーやネットワーク，データベース，またはトランザクションマネージャに障害が発生した場合に，データを失ったり，不整合な状態になったりすることは，絶対に避けなければなりません。つまり，トランザクションのACID特性を保証することが必須になります。では，2フェーズコミットを実装し
ita-wasa 2008/09/11
(4）その結果，既にコミットしたリソースマネージャとロールバックしたリソースマネージャ間でデータが不整合になります。 (5)データの不整合を解消するために，管理者がグローバルトランザクションをコミットするのか

algorithm

distributed
リンク
MIT OpenCourseWare OCW Home
Unlocking knowledge, Empowering Minds. Free lecture notes, exams, and videos from MIT. No registration required. Learn More about the OCW mission
ita-wasa 2008/09/11
skip list もあった

algorithm

document
リンク
1