NestaDB - Data Structure

１．はじめに

この文書は NestaDB for iPad（以下 NestaDB と表記）のデータ構造について記述したものである。

NestaDB のデータベースファイルは、キー・バリュー・ストアを実装したC言語の関数とデータストアを実現するための Objective-C のクラスを利用して作成されている。

下層のキー・バリュー・ストアは、ハッシュファイルと B+Treeファイルのアクセスパスが用意されており、C言語の関数として作成されている。キー・バリュー・ストアには、一般的なデータベースのテーブルやカラムの概念はなく、可変長のキーとデータをバイト配列として管理するだけである。ハッシュファイルにはシリアライズしたデータが記録されている。B+Tree はハッシュファイルのデータをキー順でアクセスしたり、ハッシュファイルのデータを検索するためのインデックスとして使用されている。
C言語で作成された関数はスレッドセーフな設計となっている。

上層のデータストアは Objective-C のクラスで作成されており、下層のキー・バリュー・ストアの上にテーブルやタプル、カラムの概念をアプリケーションに提供している。
データストア層はスレッドセーフではないため、マルチスレッドを使用する場合は呼び出し側で排他制御を組み込む必要がある。

アプリケーションは Objective-C で記述されたデータストアのAPIを利用して作成される。

２．キー・バリュー・ストア

2.1 ハッシュファイル

ハッシュファイルは .hdb の拡張子を持つファイルである。キーはハッシュ関数により指定されたバケットに保存され、バケットが指し示すポインタによってデータが記録される。
NestaDB でのバケット数は 131,062 であり、それぞれが 8バイトのデータ領域へのポインタ領域を保持している。このバケット領域は mmapシステムコールでメモリ上に配置されており、効率的なアクセスを実現している。

キーのハッシュ値にシノニムが発生した場合は、データ領域のヘッダ部を線形リストでつないでいる。

データの削除が行われた場合は、空き領域に追加して新たなデータを登録する際に再利用される。

2.2 B+Treeファイル

ハッシュファイルはキーを使用したダイレクトアクセスは効率的であるが、キー順にデータを取得することはできないため、B+Treeファイルを用意してキー順アクセスを実現している。B+Tree のデータにはハッシュファイルのプライマリ・キーを記録している。
NestaDB が使用する B+Treeファイルはキーの重複を許可している。

ファイルヘッダーにブランチノードのルートを示すポインタが格納されている。
ブランチノードとリーフノードはデータの挿入と削除によって分割・結合される。
リーフノードは双方向にアクセスできるようにリンクリストとなっている。

ノードの削除が行われた場合は、空き領域に追加して新たなノードを追加する際に再利用される。

NestaDB ではハッシュファイルの順次アクセス用とフィールド索引用の2種類の B+Treeファイルが作成される。順次アクセス用のファイルの拡張子は .bdb である。フィールド索引用のファイルの拡張子は .fdb である。

３．データストア

データストアでは一般的なファイルを表す kind とタプルを表すエンティティで構成される。
エンティティは複数のプロパティから構成されており、プロパティは name と value の形式で記憶される。エンティティは kind とエンティティIDで識別される。これがエンティティのプライマリ・キーとなる。このプライマリ・キーを使用することでエンティティに直接アクセスすることが可能となる。エンティティは可変長のバイト列として記録されるのでプロパティの数に制限はない。また、エンティティ毎にプロパティの数が違っていても問題ない。

3.1 データベースの管理

データストア内で複数のデータベースを管理するために以下のエンティティが存在している。
このエンティティがデータベースの情報を管理している。

kind: "$system"
key:  "$kindlist"

複数のプロパティがデータベースの情報を管理しており、それぞれのプロパティはデータベースIDで識別される。データベースIDは Dnn の形式であり、nn はデータストア内での連番が自動的に採用される。データベース名などの情報はプロパティ値として記録されている。

3.2 シーケンス管理

データベースIDやフィールドIDを生成するときに使用されるシーケンスを管理するエンティティが存在している。
なお、エンティティIDはシステムタイム（マイクロ秒）を使用している。

kind: "$system"
key:  "$idseq"

name:  "$dbid"
value: int64(8byte)

name:  "$fieldid"
value: int64(8byte)

3.3 フィールドの管理

データベースのフィールドはエンティティで管理されている。データベースごとに一つのエンティティが作成される。エンティティのプロパティにはフィールド名やフィールド型が記憶される。
フィールドIDは Fnn の形式であり、nn はデータストア内での連番が自動的に採用される。

kind: "$system"
key:  データベースID

name:  フィールドID
value: フィールド名やサイズなどのフィールド情報

3.4 タプルの管理

データベースのタプルは一つのエンティティとしてデータストアに記録される。エンティティのプロパティにはフィールド値が記録される。

kind: データベースID
key:  エンティティID

name:  フィールドID
value: フィールド値（バイト配列）

3.5 プライマリ・キー

タプルを順次アクセスするために B+Tree にハッシュファイルのプライマリ・キーを登録してカーソル機能を実現している。

key:   データベースID/$pkey/エンティティID
value: データベースID/エンティティID

3.6 フィールド・キー

タプルのフィールド値を検索するためにハッシュテーブルのプライマリ・キーを B+Tree に登録している。フィールドタイプが文字、数値、日付の場合のみフィールド・キーに登録される。

key:   データベースID/フィールドID/フィールド値
value: データベースID/エンティティID

Author: YAMAMOTO Naoki
Last modified: 2012/02/11