やってみた

SQLiteのファイルフォーマットを読み解いてみた

K

SQLiteのファイルフォーマットを読み解いてみた

以前SQLiteについて、公式のドキュメントDatabase File Formatを読みつつ、実際にSQLiteのファイルフォーマットをBinary Editor BZ（以下BZエディタ）を使用して検証したことがあるのでまとめてみました。
今回はデータベースファイルのファイルフォーマットに焦点を当てたいので、SQLiteの概要やデータベース作成、テーブル作成の方法などについては、割愛させていただきます。

前提条件

  • データベースは、page_size=512byteの最小サイズで作成
    • デフォルトではpage_size=4096byteです。これだと１ページ分のサイズが大きく、データを追いづらい、また図にする際に全体を載せたかったので、page_size=512の最小サイズで作成しています。
  • SQLite version 3.37.2
    • WSLのUbuntu 22.04のOS標準のSQLiteです（現在の最新ではないです）
  • 作成したデータベースの詳細（初期データ）
    • データベースファイル名　hoge.db
    • テーブル名　test001
      • 列名 num,name,prefを持つ
    • 格納したデータの内容 
      sqlite> select * from test001;
1|Tanaka Taro|Tokyo
2|Sato Jiro|Saitama
3|Suzuki Saburo|Osaka
4|Takahashi Shiro|Fukuoka
5|Yamada Goro|Aomori
  • hoge.dbファイルの入手

初期データの解析

早速ですが、作成したデータベースファイル(hoge.db)を、BZエディタを使って閲覧していきます。

BZエディタを起動 > ファイル > 開く
ファイルブラウザが開くので、事前に作成したデータベースファイルhoge.dbを選択する

下の図は、説明の都合上4色で色分けしました。

  • データベースヘッダ（上記図の黄色ハイライト部分）

    • 先頭から100 byte分
      • １ページ目だけに存在します
    • データベースのバージョンやページサイズ等の情報が含まれる

  • ページヘッダ（上記図の緑色ハイライト部分）

    • 各ページに存在する（8byteまたは12byteのb-treeヘッダ）
      • 1ページ目は、データベースヘッダの後に存在する
      • 2ページ目以降は、ページの先頭に存在する
    • ページに格納されているデータの数等の情報が含まれる

  • セルポインタ配列（上記図の青色ハイライト部分）

    • b-treeページヘッダのすぐ後に続く
      • 2byte分で1つのセル(データ)の位置を表す
    • 各セルの位置を把握している

  • セルコンテンツ領域（上記図の紫色ハイライト部分）

    • データベースに格納したデータ
    • ページ内のデータの入り方が決まっている
      • 先頭から一番遠い場所に、1番目のデータが置かれます

データベースヘッダ

データベースヘッダの各項目の意味については、公式のドキュメントのDatabese Header Formatの表と照らし合わせることで、内容が明らかになります。

本来であれば、各項目を1つずつ確認したいのですが、説明が長くなるので、ここではページサイズだけ確認する事とします。ページサイズは、前提条件に記載した通り、512byteで作成しています。
ですので、これから確認する値が、512であれば一致すると判断できます。

この表によると、Offset 16, Size 2 がページサイズを示すとあります。
実際のデータベースファイルの該当箇所は、下図の赤枠で囲った２byte分です。

その値をみると、02 00であることが分かります。
これは16進数なので、これを10進数に変換すると、512になり、意図した通りにデータベースファイルhoge.dbのページサイズが512byteで作成されていることが確認できました。

ページヘッダ

ページヘッダは、各ページに存在します。
1ページ目は、データベースヘッダの後に存在し、2ページ目以降はページの先頭に存在します。

今回のhoge.dbでは、実際に格納したデータの内容は2ページ目に存在しているので、ここからは、2ページ目（offset 200 ~ 400）のデータを参照しながら説明します。

ページヘッダも、公式ドキュメントの表B-tree Page Header Formatと照らし合わせる事で内容が明らかになります。

公式の表によると、Offset 0 size 1 が、b-tree page typeを表しているとあります。
その値をhoge.dbでみると、ODであることが分かります。

0Dは16進数なので、10進数に変換すると 13 になります。B-tree Page Header Formatの表に当てはめると、このページはbツリーページのリーフテーブルという種類であることが分かります。
リーフページの場合、8byteなので、今回は緑色のハイライト部分(8byte)がページヘッダであることが分かります。

A value of 13(0x0d) means the page is a leaf table b-tree page

ページヘッダ（緑色のハイライト部分）の値の解析結果です。

  • 0D → リーフテーブルのbツリーページである
  • 00 00 → fleeblockなし
  • 00 05 → セルの数は5 （データベースに格納したデータが5個であることを示している）
  • 01 84 → セルコンテンツ領域の開始位置 ページの先頭から388byteの位置
  • 00 → interior b-tree pageの時に値が表示される。今回はリーフテーブルなので省略されていることが分かる

セルポインタ配列

セルポインタ配列は、各セルの情報を把握しています。2byte分で1つのセルの位置を表します。
先程までで、データは５つ格納されていることが分かっているので、hoge.dbのセルポインタのそれぞれの位置は、このような結果になります。

  • 01 E9 → 489(ページの先頭から489byteの位置であることを示す)
  • 01 D2 → 466
  • 01 B9 → 441
  • 01 9C → 412
  • 01 84 → 388

この結果から、ページヘッダのコンテンツ領域の開始位置と、セルポインタの5つ目のデータが同じ位置を指している事が分かります。 これらを図にまとめると、このようになります。

ここまでで、ページヘッダには、実データの格納開始の位置や、実データの数が含まれていること、セルポインタは、各実データの位置を把握していることが分かりました。

セルコンテンツ領域

ここからは、セルコンテンツ領域を解析します。
セルコンテンツ領域には、各セル(データ)が格納されています。
今回の場合は５つのセルが格納されています。

公式ドキュメントのセルの構成は、このように説明されています。
今回の場合リーフセルなので、リーフセルの説明を抜粋しました。

Table B-Tree Leaf Cell (header 0x0d):

  -  A varint which is the total number of bytes of payload, including any overflow
  -  A varint which is the integer key, a.k.a. "rowid"
  -  The initial portion of the payload that does not spill to overflow pages.
  -  A 4-byte big-endian integer page number for the first page of the overflow page list - omitted if all payload fits on the b-tree page.

これを図にすると、セルの構成はこのようになります。

ペイロードの長さとRowIDは、可変長整数使用して格納されます。つまり正確なコンテンツの長さを知るにはvariantを算出する必要があります。
variantの算出方法は、こちらのサイトがとても参考になりました。

ペイロードの長さ

ペイロードの長さを表しているのは、今回の場合16です。 最上位ビットが立つかどうかを調べる必要があるので、16進数を2進数に変換します。

  • 16進数の値16を2進数に変換 →　00010110
    • 最上位ビットは0であり、最上位ビットは立たない

最上位ビットが立たない場合、これがvariantの最後である事を示します。つまり、00010110は22byteなので、ペイロードの長さが、22byte分であることが分かりました。

補足ですが、もしここで最上位ビットが立つ場合、２つ目の値が必要になります。2つ目も最上位ビットが立つ場合、3つ目の値が必要になります。

今回は、最上位ビットが立たなかったため、ペイロードは22byteである事が分かりましたので、次はRowIDのvariantを確認します。

RowID

  • 16進数の値05を2進数に変換 → 00000101
  • 最上位ビットは立たない

最上位ビットは立たないことが確認できたため、RowIDは5であることが分かりました。

ここまでで明確になった事をまとめ、図にすると緑のハイライトの箇所がセル１つ分（実際のデータ１つ分）であることが分かりました。

  • ペイロードの長さは 22byte
  • RowIdは 5
  • 実際のデータの開始位置は、RowIDの隣の値04の箇所から始まる(つまりペイロードヘッダの開始位置の値)

では、ここからは、その22byte分の内訳を確認します。

ペイロードヘッダ

先程までで、ペイロードヘッダの開始位置の値は04である事が分かっています。この値はペイロードヘッダの長さを表しているため、その値を含め4byte分04 0F 23 19がペイロードヘッダとなります。

  • 04 → ペイロードヘッダの長さ
  • OF → これから
  • 23 → これから
  • 19 → これから

ペイロード

ペイロードヘッダの残り３つの値 OF 23 19 については、公式ドキュメントの表Serial Type Codes Of The Record Formatとの照らし合わせが必要になります。
この残り3つという数字は、テーブルを作成した際の、列数と一致します。（列名は前提条件にも記載しましたが num,name,prefです）

OF 23 19 の値は、それぞれ、num列、name列、pref列なので、各列を解析し、格納されている値の長さを明確にします。表に照らし合わせて計算すると次のようになります。

  • num 列がどこからどこまでなのかを調べる
    • OFは16進数なので、10進数に変換 →15
    • 15を公式の表と照らし合わせると、Serial TypeがN≥13 and oddであることが分かるので、Content Sizeの計算式に当てはめると次の値が得られる
      • (15-13)/2 = 1byte
      • ページヘッダの次の値35が1byte分なので、この部分であることが分かります（下図の赤いハイライト部分）
  • name列がどこからどこまでなのかを調べる
    • 23は16進数なので、10進数に変換 → 35
    • 35を公式の表と照らし合わせて計算式に当てはめると
      • (35-13)/2 = 11byte
      • 59 61 6D 61 64 61 20 47 6F 72 6Fの11byte分(下図の黄色ハイライト部分)
  • pref列がどこからどこまでなのかを調べる
    • 19は16進数なので、10進数に変換 → 25
    • 25を公式の表と照らし合わせて計算式に当てはめると
      • (25-13)/2 = 6byte
      • 41 6F 6D 6F 72 69の6byte分(下図の緑色ハイライト部分)

図にまとめると、次のようになります。

これらの結果をまとめると、どの列にどのデータがどこまで格納されているかが明確になりました。

  • num列→ 5
  • name列 → Yamada Goro
  • pref列 → Aomori

以上、初期データの解析を終了します。

終わりに

今回は、用意した初期データが綺麗に格納されており、テーブル数やデータ数も少ないので非常に解析しやすかったのですが、実際に使い込まれているようなデータベースはテーブルが複数あり、格納されているデータ量も多く、またデータの更新、削除などを繰り返されているので複雑です。

次回またブログを書くような機会があれば、テーブルを増やし、削除したデータも含むようなデータベースを作成し解析する/しないかもしれない…

© 2016 - 2024 DARK MATTER / Built with Hugo / テーマ Stack は Jimmy によって設計されています。