Šokantis medis

Šiam straipsniui ar jo daliai trūksta išnašų į patikimus šaltinius. Jūs galite padėti Vikipedijai pridėdami tinkamas išnašas su šaltiniais.

Šokantis medis – duomenų struktūra, panaši į savaime susibalansuojančius B medžius. Šią struktūrą išrado Hansas Reiseris. Skirtingai nuo B medžio, kuris savo struktūrą visada laiko subalansuotą, šokantis medis struktūrą balansuoja tik kai duomenis prireikia išsaugoti išorinėje atmintyje (pabaigus transakciją arba dėl operatyvinės atminties trūkumo).

Kadangi balansavimo procedūra atliekama rečiau, šia struktūra pagrįsti algoritmai yra greitesni. Be to, pati balansavimo procedūra tada gali būti ilgesnė ir labiau optimizuojanti.

Šokančio medžio pagrindu sukurta atviro kodo failų sistema Reiser4 su mažais (apie 1 kilobaito didumo) failais gali būti net iki 15 kartų greitesnė nei dabar GNU/Linux labiausiai paplitusi EXT3.