前回は,
ブロックの拡張問題
前回,
表1 FINDSPOTの転置インデックスのブロック構造
レコード位置 | 内容 |
---|---|
0 | ブロックサイズ |
1 | 見だし語 |
2 | データ1 |
3 | データ2 |
4 | データ3 |
5 : : : |
データ4 : : : |
このブロックには,
転置インデックスの作成当初は対象とする文書数が少ないので,
FINDSPOTの初期の実装
FINDSPOTの初期の実装では,
表2 初期のFINDSPOTの転置インデックスのブロック構造
レコード位置 | 内容 |
---|---|
0 | ブロックサイズ |
1 | 見だし語 |
2 | 次のブロック位置 |
3 | データ1 |
4 | データ2 |
5 | データ3 |
6 : : : |
データ4 : : : |
最初に作成するブロックは16レコード分です。この時,
また,
表3 ブロック数とデータ数の関係
ブロック数 | レコードサイズ | 格納できるデータ数 |
---|---|---|
1 | 16 | 13 |
2 | 16 | 26 |
3 | 16 | 39 |
4 | 16 | 52 |
5 | 16 | 65 |
6 | 32 | 94 |
7 | 32 | 123 |
8 | 32 | 152 |
9 | 32 | 181 |
10 | 32 | 210 |
11 | 64 | 271 |
12 | 64 | 332 |
13 | 64 | 393 |
14 | 64 | 454 |
15 | 64 | 515 |
16 | 128 | 640 |
17 | 128 | 765 |
18 | 128 | 890 |
19 | 128 | 1015 |
20 | 128 | 1140 |
21 | 256 | 1393 |
22 | 256 | 1646 |
23 | 256 | 1899 |
24 | 256 | 2152 |
25 | 256 | 2405 |
26 | 512 | 2914 |
27 | 512 | 3423 |
28 | 512 | 3932 |
29 | 512 | 4441 |
30 | 512 | 4950 |
31 | 1024 | 5971 |
32 | 1024 | 6992 |
33 | 1024 | 8013 |
34 | 1024 | 9034 |
35 | 1024 | 10055 |
36 | 2048 | 12100 |
37 | 2048 | 14145 |
38 | 2048 | 16190 |
39 | 2048 | 18235 |
40 | 2048 | 20280 |
41 | 4096 | 24373 |
42 | 4096 | 28466 |
43 | 4096 | 32559 |
44 | 4096 | 36652 |
45 | 4096 | 40745 |
46 | 8192 | 48934 |
47 | 8192 | 57123 |
48 | 8192 | 65312 |
49 | 8192 | 73501 |
50 | 8192 | 81690 |
51 | 8192 | 89879 |
52 | 8192 | 98068 |
53 | 8192 | 106257 |
この表によると,
このブロック数を拡張する方法は,