DBMによるテーブルデータベース - mixi engineer blog
正月早々インフルエンザにかかって寝込んだmikioです。電車に乗る時や繁華街などに出る時はマスク着用が必須ですね。さて今回は、Tokyo Cabinetで実装したテーブル方式のデータベースについて紹介します。意外にどうして強力な機能なので、このネタは連載することを予告します。 テーブルデータベースとは 簡単に言えば、リレーショナルデータベースのテーブルのように、複数の列からなるレコードを格納できるデータベースです。SQLや表結合などの複雑な機能はサポートしませんが、そのぶん高速に動作します。つまり、DBMの速度で動くリレーショナル風データベースです（厳密にはリレーショナルデータベースではありません）。 TCの基本となるハッシュデータベースは、単純なkey/value型のデータベースであり、つまりキーにも値にもスカラ（数値や文字列などの特に構造を持たない単一の値）しか格納することはできません
mixi Engineers’ Blog » Inside Tokyo Cabinet その弐
予定を立てた途端にやりたくなくなる症候群に堪えて連載を続けるmikioです（こんな私でもエアーマンくらいは倒せます）。前回はDBMの基本について説明しましたが、それを忠実に実装しても実際には使いものにはならないことにも触れました。今回は、実用的なDBMに進化すべく、Tokyo Cabinet（およびその前身のQDBM）で考えた工夫についてお話します。 ハッシュ関数についてもう少し 前回の記事に関して、「ハッシュ関数はビットシフト使って実装した方が早いよ」という旨のお便りをいただきました（ありがとうございます）。まさにその通りで、乗算命令（ここではimull）より左シフト命令（ここではsall）の方が速いみたいです（Intelの資料によると、mulが15から18で、salが4とのこと）。しかし、DBMの場合はファイルI/Oにかかる時間が支配的になるというのが重要な点です。したがって、ハッシュ
Inside Tokyo Cabinet その壱 - mixi engineer blog
約半年間の沈黙を破ってOSSの世界に戻ってきつつあるmikioです。先日、Tokyo Cabinet（以下「TC」と呼びます）というデータベースライブラリをリリースしました。今回から数回に分けて、TCの設計と苦労話について連載してみます。 DBMとは TCは、いわゆるDBMの系譜のデータベースライブラリで、単純なハッシュテーブルをファイル上で永続化するだけの機能を提供します。DBMはAT&Tの古代UNIXの時代から受け継がれる伝統芸能なのですが、私はそういう枯れた技術が大好きなのです。 プログラマの皆さんは、PerlやRubyではハッシュ（連想配列）と呼ばれ、JavaやC++ではmapと呼ばれるような、何らかのキーに関連づけてなんらかの値を記録するデータ構造って実によく使いますよね。例えばmixiでは、ユーザアカウントに関連する情報（名前とかニックネームとか）は、ユーザIDをキーにしたハッ
mixi Engineers’ Blog » 圧縮データベースを使おう
チャリンコ通勤による滝のような汗で、朝からTシャツがシースルーになってしまうmikioです。さて今回は、Tokyo Cabinet（TC）のデータベースを各種のアルゴリズムで圧縮して利用する方法についてご紹介します。 圧縮B+木 B+木とは、比較関数の値による順序が近いレコード群を単一のページにまとめ、各ページにB木（multiway balanced treeの略であり、二分木（binary tree）とは違います）の索引を張ったものです。理論的にはレコードの探索も更新も O(log n) の時間計算量で行え、内部ノード（B木）の操作をキャッシュすると実質的には O(1) の時間計算量で探索や更新が行えるという、かなり安定した性能を備えるデータ構造です。その上、レコードが一定の順序に基づいて並べられているので、数値の範囲検索や文字列の前方一致検索が高速に行えたり、カーソルによって順序に基
mixi Engineers’ Blog » 言語バインディングを書こう
世田谷の某所から原宿まで自転車通勤しているのですが、そろそろ寒くなってきたので電車に切り替えようかと悩み中のmikioです。今回はTokyo Cabinetのスクリプト言語バインディングについて述べます。 スクリプト言語バインディングとは TCはC言語で実装されたライブラリで、C言語（C89、C99）およびC++言語のプログラムから利用することができます。CやC++は各種の計算処理やシステムコールの呼び出しを直接的に記述できるので高速に動作するプログラムを作ることができる反面、ポインタ演算やメモリ管理などで致命的なバグを潜ませやすいので非常に注意深くコーディングを進めなければいけません。つまり、プログラムの実行速度は速いが、開発速度は遅いということです。 それに対して、PerlやRubyをはじめとするいわゆるスクリプト言語は、実行速度はCやC++に劣るものの、高水準かつ直感的な文法と強力な
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
