SILO再考〜次世代DBのアーキテクチャとして - 急がば回れ、選ぶなら近道
大分たってしまったけど、ようやく時間が空いたので、db tech showcase Tokyo 2016 http://enterprisezine.jp/dbonline/detail/8466 で話した内容を記録的に書いておく。あとはSILOの解説を特に自分用に論文の4章を中心に整理しておく。あとはついでに自分の思うところも記す。 ・SILO 元論文はこちら、執筆陣はMITのLiskov一派とEddie Kohler 現在のDB研究の第一線のメンバー。 http://people.csail.mit.edu/stephentu/papers/silo.pdf SILO以降、大きくDBベースのアーキテクチャの考え方は変わりました。ほとんど全ての分散系OLTPはSILOを程度の大小はあるとはいえ、意識していると言っても過言ではないでしょう。前世代ではほぼ「空想か？」ぐらいの扱いだった分散t
Bloom filter - Wikipedia
In computing, a Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed (though this c
mixi Engineers’ Blog » Inside Tokyo Cabinet その五
先日、MySQL Conferenceという催しに行ってきました。そこでMySQLの開発者のBrian Aker氏およびMichael Widenius氏と話をする機会があったのですが、やっぱしトップランナー達と議論するのは刺激になるなぁと思ったmikioです（その時の資料）。さて、一連の連載も今回が感動の最終回で、TCの性能上の蘊蓄をお届けいたします。 なぜdynamic hashingを使わないか Brianさん達とTCの実装についても少し議論したのですが、その際にdynamic hashingをなぜ使わないのかと問われました。その背景として、TCやQDBMではハッシュのバケット数（＝格納するレコード数を予測してその数倍に設定すべき値）をデータベース作成時に指定しなければならないという問題があります。バケット数が大きすぎると空間効率が劣化し、小さすぎると時間効率が劣化するというトレード
mixi Engineers’ Blog » 圧縮データベースを使おう
チャリンコ通勤による滝のような汗で、朝からTシャツがシースルーになってしまうmikioです。さて今回は、Tokyo Cabinet（TC）のデータベースを各種のアルゴリズムで圧縮して利用する方法についてご紹介します。 圧縮B+木 B+木とは、比較関数の値による順序が近いレコード群を単一のページにまとめ、各ページにB木（multiway balanced treeの略であり、二分木（binary tree）とは違います）の索引を張ったものです。理論的にはレコードの探索も更新も O(log n) の時間計算量で行え、内部ノード（B木）の操作をキャッシュすると実質的には O(1) の時間計算量で探索や更新が行えるという、かなり安定した性能を備えるデータ構造です。その上、レコードが一定の順序に基づいて並べられているので、数値の範囲検索や文字列の前方一致検索が高速に行えたり、カーソルによって順序に基
blog.katsuma.tv
greeさんで開催されたKey Value Store勉強会に行ってきました。 時間にして4時間超え、内容も国内のKey-Value Storeなソフトウェアの最前線の話ばかりで相当なボリューム。以下、メモってたのを残しておきたいと思います。（誤字、脱字、内容に誤りを含むものなどありましたらお伝えください）また、発表者の方やプロダクトについて、ざっくり調べてURL見つけられたものについてはリンク張っています。 森さん / 末永さん groonga Sennaの後継エンジン 融通が効かないのがSennaのデメリット スコア算出式のカスタマイズなど Sennaの転置索引 索引の構成部品を自由に組み合わせて使える APIもいろいろ QL DB Low Level memcached互換のkey-value store バイナリのみ対応 計測 クライアント memstorm-0.6.8 mem
インデックスの基礎知識
■ インデックスとは データベースの世界で、インデックス(索引)とはテーブルに格納されているデータを 高速に取り出す為の仕組みを意味します。 インデックスを適切に使用することによってSQL文の応答時間が劇的に改善 される可能性があります。 インデックスにはB-Treeインデックスをはじめ、ビットマップインデックス、 関数インデックスなどの種類がありますが、ここでは最も一般的に使われ、かつ ほとんどのDBMSでサポートされているB-Treeインデックスについて解説します。 ※ CREATE INDEX文でオプションを指定しない場合は通常B-Treeインデックスが 作成されます。 ■ B-Treeインデックスのしくみ B-Tree(Balanced Tree)インデックスは次のようなツリー状の構造になっています。 ツリーの先頭はヘッダブロックと呼ばれています。ヘッダブロックでは、キー値の 範囲
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Amazon.co.jp: トランザクション処理 上: ジムグレイ, アンドレアスロイター: 本
