m-rajaline otsimispuu, B-puu.
B-puu
Kahendotsimise puud võib üldistada m>2 juhtumile, lubades ühes puu tipus hoida kuni m-1 kirjet (m on konstant).
m-rajaline otsimispuu on kas:
1. tühi või
2. koosneb juurest, milles hoitakse järjestatuna j võtit (0<=j<m) ning j+1 alampuust, mis kõik peavad olema kas mittetühjad m-rajalised otsimispuud või (kõik) tühjad puud. Juure võtmete k1 <= k2 <= ... <= kj ja alampuude T0, T1, ... , Tj jaoks kehtivad järgmised kitsendused:
1. kõik alampuus T0 esinevad võtmed k ei ületa juure esimest võtit k1: k <= k1
3. kõigi võtmete k jaoks alampuust Ti (0<i<j) kehtib ki <= k <= ki+1
4. kõik alampuus Tj esinevad võtmed k pole väiksemad kui juure viimane võti kj: k >= kj
m-järku B-puu (Bayer, McGreigh) on niisugune m-rajaline otsimispuu, milles
1. kõik lehed on samal tasemel;
2. lehed ei sisalda võtmeid (fiktiivsed, edaspidi jätame joonistel kujutamata);
3. juurel on 2 kuni m alluvat;
4. kõigil teistel vahetippudel on t=ceil[m/2] (t>=2) kuni m alluvat.
Seega on juures 1 kuni m-1 võtit, vahetippudes t-1 kuni m-1 võtit.
Tipp on täitunud, kui ta sisaldab m-1 võtit.
Kõrgus h <= log t ((n+1)/2)
Mahutavus n ~ O (2*(m/2)h)
3-järku B-puu = 2-3 puu (igal vahetipul 2 või 3 alluvat).
Otsimine: O(th)
Lõigu "poolitamise" asemel otsitakse õigest alamlõigust (igal sammul kuni m valikut, kuni h sammu).