トランスポート層とTCP/IP
最初に簡単に転送速度の例題の解説。
毎年、意外と間違いが多いのが、異なる速度のネットワークを経由した転送時間。パケットは、バケツリレー方式で送られるので、通信路の一番遅い部分の通信速度で計算すればいい。
サブネット同士をつなぐプロトコルとして、IPプロトコルを紹介したが、データ通信ではノイズなどの影響で通信に失敗することがある。これらを補うためのTCPがある。
TCP
TCP(Transmission Control Protocol/トランスミッションコントロールプロトコル)では、分割されたパケットを元の順序に組み上げたり、パケットが途中で消えた場合の再送などの処理を行う。この機能により確実に相手に送る機能が実現されている。
3way ハンドシェーク
TCPの通信では、最初に相互に通信が可能かを確認するハンドシェークが行われる。パケットには、SYN,ACK,FINといった種別を表すフラグがついており、SYNは接続確立の要求を表す。ACKは了解を表す。FINは切断要求を表す。通信開始の時には、(1)通信OK?,(2)OKだよ、そっちもOK?,(3)OKだよ!といった3つの通信パケットで確認してから通信を行う。この最初のやり取りを3way ハンドシェークという。
B木の構造とデータベース
2分探索木の考え方を拡張したもので、B木がある。
B木の構造
B木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータd0..d2N-1と、2N+1本のポインタp0..p2Nから構成される。piの先には、di-1<x<di を満たすデータが入った B木のノードを配置する。ただし、データの充填率を下げないようにするため、データは最小でもN個、最大で2N個を保存する。
B木からデータの検索
データを探す場合は、ノード内のデータ diの中から探し、見つからない場合は、ポインタの先のデータを探す。位数がある程度大きい場合、ノード内の検索は2分探索法が使用できる。また、1つのノード内の検索が終われば、探索するデータ件数は、1/N〜1/2Nとなることから、指数的に対象件数が減っていく。よって、検索時間のオーダは、O(N) O(logN) 資料修正注意となる。 (さらに…)