AVL木

AVL木（AVL-tree）とは、どの節点においても、「その左部分木の高さ」と「右部分木の高さ」の差が1以下となる木のことです。

B木

リーフにしかキー値を持たないので、探索に必要な読み込みブロック数（計算量はほぼこれで決まる）は、木の高さによって決まります。
リーフまでの距離が一定ということは、どのキーを使っても探索を同じ計算量で行えるということなので、検索や更新にかかる時間がキー値によらず一定になります。