豪鬼メモ

一瞬千撃

Search Result: DBMの設計と実装 その

DBMの設計と実装 その21 実装作業に向けて

長きに渡った集中連載もこれでひとまずは終了である。過去ログはこちらを見てね。最後に実装作業の計画についてまとめておこう。

DBMの設計と実装 その20 セカンダリインデックス

DBMをRDBMS風に使うためにセカンダリインデックスを使いたくなる場合もあるかもしれない。その設計と実装について考えてみたい。

DBMの設計と実装 その19 バックアップ

DBMでサービスを提供している最中に、データベースファイルのバックアップを取りたくなることがあるだろう。当然、サービスのダウンタイムにならないように、データベースにアクセスする他のスレッドはブロックしないで行いたい。それにはどうするか。

DBMの設計と実装 その18 アトミックなレコード処理

私が設計したDBMに特徴的な機能である、アトミックなレコード処理について詳しく紹介したい。以前誰かがデータベースのクンフーであると言ってくれた面白い機能だ。

DBMの設計と実装 その17 ゾーンI/O

ファイルI/Oの実装として、ファイルの内容に同期したメモリ上の領域にアクセスするメモリマップI/Oを利用する際のインターフェイスについて考察する。

DBMの設計と実装 その16 オンメモリデータベース

DBMのインターフェイスでオンメモリのストレージを実現できる。その設計と実装について考えてみよう。

DBMの設計と実装 その15 スキップデータベースの検索

スキップデータベースを検索するアルゴリズムの要点について考えてみる。メモリ確保の戦略が重要になってくる。

DBMの設計と実装 その14 スキップデータベースの書式

ソート済みのレコードの連結リストにスキップリストを付与したものがスキップデータベースである。その具体的な書式についてここで完全に定義する。

DBMの設計と実装 その13 スキップリストの構造

ハッシュデータベースとツリーデータベースの設計については一段落したので、次にスキップリストデータベースの設計に移る。まずはスキップリストの概要についてまとめてみよう。

DBMの設計と実装 その12 ツリーデータベースの実装

ツリーデータベースを実装するにあたり、具体的にどういうデータ構造を使うかを検討する。並列化についてもここで検討する。

DBMの設計と実装 その11 ツリーデータベースの書式

ハッシュデータベースを基盤に構築したB+木のデータベースを、以後、ツリーデータベースと呼ぶ。データベース全体のメタデータとして何を持つべきか、B+木の各ノードはどのようなデータを持つか、またどのようにシリアライズするか、ここで完全に詰めて定義する。

DBMの設計と実装 その10 LRUキャッシュ

B+木をファイル上で実現するにあたり、個々のノードのデータをシリアライズしてハッシュテーブルのDBMに格納するということを前回述べた。そして、個々のノードにアクセスする度にハッシュDBMの読み書きをすると遅すぎるので、キャッシュ機構が求められる。そのキャッシュ機構の設計をしてみたい。

DBMの設計と実装 その9 B+木の構造

B+木を使ったデータベースの設計をしよう。これを使うと、レコードの順序に基づいた検索ができる。範囲検索とか、前方一致検索ができる。その基本的な構造について考察する。

DBMの設計と実装 その8 ファイルクラス毎の性能

前回設計した4つのファイル具象クラスを実装し、その性能を測ってみた。

DBMの設計と実装 その7 ファイルの抽象化

データベースと呼ばれるシステムは大抵、ファイルにデータを記録する。DBMも例外ではない。でも、ファイルって何だろう。ここでちゃんと考えてみたい。

DBMの設計と実装 その6 ハッシュデータベースの再構築

ハッシュデータベースをオンラインで再構築する方法について検討してみる。オンラインというのはすなわちサービスを提供しながら、ダウンタイムを発生させずに行う処理である。

DBMの設計と実装 その5 ハッシュデータベースの書式

前回はハッシュデータベースの大まかな構造を述べたが、今回はデータフォーマットの形式を完全に詰める。

DBMの設計と実装 その4 ハッシュデータベースの構造

ハッシュテーブルを使ったデータベースの構造について大いに語ってみよう。基本的な構造について述べてから、インプレース更新と追記更新の違いについて明らかにする。

DBMの設計と実装 その3 ハッシュロック

今回の設計の要点の一つは、並列性である。ハッシュテーブルを保護するにあたって利用するスロットロック法について考察してみたい。

DBMの設計と実装 その2 APIの草案

DBMのAPIをほぼ決めて文書にまとめた。その解説をしよう。文書はここに置いてある。

DBMの設計と実装 その1 ハッシュ関数

個々のレコードがハッシュテーブル内のどのバケットに属するかはハッシュ関数で決める。入力値の種類によらずハッシュ値がうまいことばらけて衝突が起こりにくい関数が良い。今回は定番のMurmur hashを採用した。Rubyの文字列型のハッシュ関数もこれだ。

DBMの設計と実装 その0 全体の計画

DBMの設計と実装について20回くらいに分けて書いてみる。まずは全体の計画と意気込みから。