040 余談になります
●040 余談になります
スクリプトがアロケーションファイルを調べている間が手持ち無沙汰だ。Ｂツリーの実装が気になって、インデックスノードについて調べてみた。
インデックスノードはこのＨＤＤの場合、全部で 16 個ある。インデックスノードの先頭部分を抜粋して表示しよう。「＝」の左側の数字はノード番号で、「＝」の右側が先頭部分の情報です。
_168 = { 'fLink': ___0, 'numRecords': _15, 'height': 3, 'bLink': ___0 }
_975 = { 'fLink': _167, 'numRecords': _80, 'height': 2, 'bLink': ___0 }
_167 = { 'fLink': _338, 'numRecords': _73, 'height': 2, 'bLink': _975 }
_338 = { 'fLink': _498, 'numRecords': 175, 'height': 2, 'bLink': _167 }
_498 = { 'fLink': _668, 'numRecords': 140, 'height': 2, 'bLink': _338 }
_668 = { 'fLink': 1523, 'numRecords': 148, 'height': 2, 'bLink': _498 }
1523 = { 'fLink': _847, 'numRecords': _78, 'height': 2, 'bLink': _668 }
_847 = { 'fLink': _991, 'numRecords': 148, 'height': 2, 'bLink': 1523 }
_991 = { 'fLink': 1144, 'numRecords': 121, 'height': 2, 'bLink': _847 }
1144 = { 'fLink': 1271, 'numRecords': 115, 'height': 2, 'bLink': _991 }
1271 = { 'fLink': 1571, 'numRecords': 123, 'height': 2, 'bLink': 1144 }
1571 = { 'fLink': 1422, 'numRecords': 114, 'height': 2, 'bLink': 1271 }
1422 = { 'fLink': 1739, 'numRecords': 127, 'height': 2, 'bLink': 1571 }
1739 = { 'fLink': 1958, 'numRecords': 201, 'height': 2, 'bLink': 1422 }
1958 = { 'fLink': ___3, 'numRecords': __1, 'height': 2, 'bLink': 1739 }
___3 = { 'fLink': ___0, 'numRecords': __3, 'height': 2, 'bLink': 1958 }
ヘッダーノードに記録されているルートのノード番号は 168 である。上記の一番上ですね。
ルートの「高さ（height）」は 3 になっている。高さというのはＢツリーの木構造の段数のこと（...教科書によっては「深さ」という用語を使うことも）。
ルートの「レコード数（numRecords）」は 15 になっている。ルートには 15 個のレコードがあり、各レコードの中にキー情報とポインタ（ノード番号）が 1 組、格納されている。つまり、ルートのノードの配下に 15 個のインデックスノードがリンクされているわけだ。この 15 個が上記の 2〜16 番目ですね。
これら 15 個のノードの高さは、ルートより 1 段下がって、2 になっている。さらにインデックスノードの各々の下にリーフノードが計 1647 個リンクされていて（...3 + 1 + 201 + 127 + ... + 80 で計 1647 個です）、リーフノードの高さは 1 になる。リーフノードが木の末端で、葉っぱで、最下段です。
ルート（根）が高さ 3 で、リーフ（葉）が高さ 1 と、本来の木とは上下が逆さまなのは、計算機科学の伝統です。教科書でもルートを上した図が載っています。教科書によってはルートの高さを 1（または 0）として、リーフに向かって数が増えるように表現しているものもありますけれど、図を描くときにはルートを上にしていて、これが慣習だとしている点は同じですね。
ルートが上でよいのか？という疑問については、Knuth という偉い学者先生が木は根が上の方が書き易いと言っていて、まぁ、Knuth 先生がそう言うならそれでよいと思います。
それと、fLink と bLink はポインタで、ノード番号が格納されていて、これにより同じ高さのノードは双方向リストになっている。双方向リストの最初の bLink と最後の fLink には 0 が入っている。
高さ 3 のノードは 1 個しかないので fLink も bLink も 0 になる。
高さ 2 のノードは、975 番が最初のノードで、3 番が最後のノード。fLink や bLink はインデックスノード内のレコードが一杯になるなどで、木構造を調整する時に使うのでしょうか。
＊＊＊
インデックスノードのレコードにはキー情報（親フォルダのＩＤとファイル名（またはフォルダ名））とポインタ（ノード番号）が格納されている。これを使ってＢツリーを探索する。
その際、同じ高さのノードで、最初のノードの最初のレコードのキー情報が最小で、最後のノードの最後のレコードのキー情報が最大となるように、その間のノードのレコードも同様に昇順になるように並べられている。
そして、Ｂツリーの探索は、例えば、インデックスノードに格納されているレコードが 3 個として、そのキー情報とポインタを｛K1, P1｝と｛K2, P2｝、｛K3, P3｝として、探索したいキーを k とすると、
K1 ≦ k ＜ K2 なら、P1 でリンクされたノードにいく
K2 ≦ k ＜ K3 なら、P2 でリンクされたノードにいく
K3 ≦ k なら、P3 でリンクされたノードにいく
これをリーフノードにたどり着くまで繰り返す。なお、k ＜ K1 の場合には検索したキーに対応するデータは存在しないことを意味する。
TN1150 で注意書きしているように、教科書的なＢ木は N 個のキーと N+1 個のポインタを持ち、キーが K1, K2 の 2 個、ポインタが P1, P2, P3 の 3 個とすると、k ≦ K1 なら P1 を、K1 ＜ k ≦ K2 なら P2 を、K2 ＜ k なら P3 をたどるのですね。
あと、データがリーフノードのみにある点も Bayer 達が提案した最初のＢ木と違い、改良版になっている（...Ｂ木の改良版は「Ｂ+木」とか「Ｂ*木」とか言うそうだ）。データはリーフノードのみにすることで、インデックスノードの個数を減らせる。
これが教科書で勉強したＢ木なのですね。
＊＊＊
夜はまだ長い。ディスクのアクセスランプがチラチラと光るのがちょっとまぶしい。
＊＊＊
このＨＤＤの場合、ルートのノードから探索開始して目的とするリーフノードに到着するまでに、最悪ケースで、log2(15) + log2(201) = 11.55 回のキー情報の比較と 3 回のディスクアクセスが発生する。
Ｂツリーを構成せずにリーフノードのみを二分探索したら、リーフノードは 1647 個あるので、log2(1647) = 10.68 回と 10 回余のディスクアクセスとなる。キー情報の比較回数は少ないが、ディスクアクセス回数が多い。
メモリ上で行うキー情報の比較よりも時間を要するディスクアクセス回数を減らせることがＢ木のポイントですね。「算法序論」の教科書でＢ木のページでいきなり、トラックやヘッダーなど磁気ディスクの構成を図示して、ディスクの回転速度を説明し始めたのはこの為でした。
＊＊＊
インデックスノード 1958 番のレコード数が 1 個で、ノード 1739 番のレコード数が 201 個とバランスが悪いように見える。Ｂツリーではルートからリーフまでの段数が重要なので、余り気にしなくてよいのですが、気になります（...木のことだけに？）。
ノード 1958 番とノード 1739 番は（高さ 2 の双方向リンクで）隣同士なので、ノード 1739 番のレコードをノード1958 番に少し移しても良さそうです。逆にノード 1958 番のレコード 1 個を 1739 番に移動すればノード数を減らせます。この外付けＨＤＤを M0c に接続したら、空き時間でカタログファイルの整理をし始めたりしないでしょうか。あるいはノード 1739 番の配下に収容されるファイルを意図的に増やしたら、インデックスノードの整理が始まるはずです。
教科書にはインデックスノードの調整について、幾つかの方法が説明されている。木の高さを減らす調整が重要だけど、レコード数の調整についても、1/2 や 2/3 をしきい値として、これを越えるまでは調整を遅延させる云々とか。その実例が目の前にあると思おうと手を出したくなる。
私「しきい値を調べてみたい。リーフで増減があると、その上のインデックスノードに影響して、更にその上へと連鎖するところとか観察したいな。あー、時間があったらですね」（...今がどんな状況なのか思い出したようだ）
TN1150 でも「ボリュームフォーマット仕様は楽しい」と言っているし、ドキュメントを読んで、その実際を調べて、勉強したことが利用されているのを確認できるのは楽しい（...いや疲労困憊すると書いてあるけど、本心では楽しいの？）。
＊＊＊
なお、このＨＤＤは 2 TB（2,000,398,934,016 バイト）で、1 ブロック 4KB とすると、1D1C1116h 個のブロックになる。ＬＢＡ１−０３って良いよね。
ＨＤＤの最初のブロック（#0）はＭＢＲ。これは古いＯＳがＧＰＴのＨＤＤにアクセスしたときに誤って破戒されることを防ぐためのダミーのＭＢＲで、保護ＭＢＲと言う。その次にＧＰＴのヘッダ（#1）とパーティションエントリ（#2〜#5）が続く。
このＨＤＤの場合、パーティションエントリには 2 個の領域が登録されていて、1 個目は EFI System、2 個目が HFS Plus。
領域１： _______#6h 〜 ___#12C05h まで、___12C00h ブロック
領域２： ___#12C06h 〜 #1D1B9110h まで、1D1A650Bh ブロック
未割当： #1D1B9111h 〜 #1D1C1110h まで、____8000h ブロック
あと、ディスク末尾の #1D1C9111h 〜 #1D1C9115h はＧＰＴのヘッダとパーティションエントリのミラーデータである。
ＨＤＤの全体が /dev/sdb でアクセスでき、領域２が /dev/sdb2 でアクセスできる。それで /dev/sdb のブロック #12C06h をリードするのと /dev/sdb2のブロック #0 をリードするのは、同じブロックをアクセスすることになる。
もしもＯＳがＨＤＤの領域を認識せず、デバイスファイル /dev/sdb2 等ができなかった場合には、/dev/sdb にアクセスしてＭＢＲとＧＰＴを読み出して、HFS Plus の領域（#12C06h 〜）を特定するところから始めることになるね。
＊＊＊
友「ＧＰＴは GUID Partition Table の頭文字です。GUID は Globally Unique Identifier の頭文字ね」
私「えー、GNU P.T. だと思ってた。頭文字と言えば、あたま...Ｄ、言え、何でももないです」
友「夜になったら早く寝るのがよいと思います」
私「あ、はい。おやすみなさい」
＊＊＊
