前回は，FINDSPOTの転置インデックスの構造について説明しました，今回はこの構造に至った経緯などについて解説します。

ブロックの拡張問題

前回，転置インデックスのブロックは次のような構造になっていることを説明しました。

このブロックには，ブロックサイズがいっぱいになるまで（空きレコートが存在する間）は，データを詰め込むことができますが，ブロックが溢れてしまって，これ以上データが格納できない場合にどうするかという課題があります。

転置インデックスの作成当初は対象とする文書数が少ないので，転置インデックスに登録するデータ量は少ないのですが，だんだん登録する文書数が増えていくと，転置インデックスに登録しなければならないデータ量も大きくなっていきます。必然的に，特定のN-gramに関する転置インデックスのレコードが溢れることになり，この時にどのように対処すべきかという問題が発生するのです。

FINDSPOTの初期の実装

FINDSPOTの初期の実装では，ブロックが溢れたら，続きのデータを格納するために新たに別のブロックを作成する方式を採っていました。この時，続きのデータ用のブロック位置に関する情報は，ブロックの第2番目のレコードに格納していました。

最初に作成するブロックは16レコード分です。この時，ブロックサイズ，見だし語，次のブロック位置のために3レコードを消費するので，都合13レコード分がデータ用に利用できます。このブロックには13個分のデータを書き込めますが，次に14個目のデータを同じN-gramに関して書き込む必要が生じたら，新たなブロックを作成して，14個目のデータを書き込むという寸法です。新たなブロックの転置インデックス内の位置は，元のブロックの第2レコードに書き込むことで，検索の際には，このチェーンを辿って次のブロックを参照できます。

また，ブロックのサイズに関しては，最初は16レコード分のブロックサイズ（128バイト）とし，続きのデータ用のブロックは5個ごとにサイズを倍に拡張するというアルゴリズムを使用していました。次の表は，このブロック拡張によって，トータルで何個のデータが格納できるかを示したものです。

この表によると，1000個のデータを格納するには19個のブロック，1万個のデータを格納するには35個のブロック，10万個のデータを格納するには53個のブロックが必要になることがわかります（表中色のついた箇所）。

このブロック数を拡張する方法は，使用されていない空きレコードが少ない（最大でも最後に作成したブロックの空きレコード分）ことや，データを追記する際の処理が軽くて済むというメリットがあります。実際に使用してみたところ，転置インデックスの作成スピードは十分でしたが，検索性能に関してはもうひとつ満足のいくものではありませんでした。