B-үйінді - B-heap

A B-үйінді Бұл екілік үйінді кіші ағаштарды бірыңғай ұстау үшін жүзеге асырылады бет. Бұл пайдалану кезінде үлкен үйінділер үшін қол жетімді беттер санын он есеге дейін азайтады виртуалды жад, дәстүрлі жүзеге асырумен салыстырғанда.[1] Элементтерді дәстүрлі картаға орналастыру массив әр деңгейді әр түрлі параққа қояды.

Компьютерлерде виртуалды жадыны немесе кэшті пайдаланатын тиімді басқа да нұсқалар бар ескертусіз алгоритмдер, үйінділер,[2] және ван Эмде Боастың орналасуы.[3]

Мотивация

Дәстүр бойынша екілік ағаштар а сәйкес дәйекті жадыда орналастырылған n -> {2n, 2n + 1} ереже, егер түйін орнында болса n, оның сол және оң баласы позицияларда болуы керек 2n және 2n + 1 массивте. Түбір 1-ші позицияда. Екілік ағаштардағы әдеттегі операция - вертикальды өту; ізделген түйінге жету үшін ағаш деңгейлерінен төмен түсу. Алайда, қазіргі заманғы компьютерлерде жадыны виртуалды жадтағы беттерге орналастыру әдісі болғандықтан, екілік ағашты орналастырудың бұл схемасы өте тиімсіз болуы мүмкін. Себебі, ағаштың тереңінен өткенде, келесі түйінге дейінгі арақашықтық геометриялық прогрессиямен өседі, сондықтан алынған әрбір келесі түйін жеке жад парағында болады. Бұл олардың санын көбейтеді бет жіберіп алды B-үйіндісі бұл проблеманы жадтағы түйіндерді басқа жолмен орналастыру арқылы мүмкіндігінше бір параққа ішкі ағаштарды орналастыруға тырысады. Демек, тік өтпелі қозғалыстың жалғасуы кезінде бірнеше рет алынған түйіндер бір парақта орналасып, парақ жіберіп алудың аздығына әкеледі.

Іске асыру

Толығырақ, b-үйінді келесі жолмен жүзеге асырылуы мүмкін. Пул-Хеннинг Камп[4] түйіндердің орналасуының екі нұсқасын ұсынады: бір парақта екі позиция босқа кетеді, бірақ ағаштың қатаң екілік құрылымы сақталады, ал екіншісі парақтардың барлық кеңістігін пайдаланады, бірақ ағаш кеңейе алмайды. жаңа бетке кірген кезде бір деңгей үшін (сол деңгейдегі түйіндерде бір ғана бала болады). Қалай болғанда да, маңызды мәселе, парақтан шыққан кезде екі түйін әрқашан жалпыға бірдей басқа бетте болады, өйткені вертикальды трансверсте алгоритм әдетте екі баланы да ата-анасымен қалай салыстыруға болатындығын біледі. Осы себепті әр парақта бір-бірімен қиылысқан екі параллель кіші ағаш бар деп айтуға болады. Парақтардың өзін а м-ағашы, және әр парақтағы элементтердің жартысы жапырақ болатындықтан (парақ ішінде), «беттер ағашында» бөліну коэффициенті болады беттер / 2.

Ата-ана функциясы

Массив тәрізді классикалық орналасудан айырмашылығы, B-үйіндісіндегі ата-ана функциясы күрделі, өйткені түйіннің ата-анасының индексі оның қай жерде орналасқанына байланысты әр түрлі есептелуі керек. Егер парақтың ішіндегі позициялар 0-ден таңбаланса парақ, ата-аналық функция келесідей болуы мүмкін.

0 және 1 түйіндері үшін олар тек барлық мүмкіндікті пайдаланатын нұсқада қолданылады. Бұл жағдайда екі түйіннің де ата-аналық индексі бірдей, ол басқа бетте орналасқан және оның сол парақтағы нақты ығысуы тек ағымдағы бет нөміріне байланысты болады. Нақтырақ айтқанда, ата-ананың бет нөмірін есептеу үшін, ағымдағы түйіннің бет нөмірін «бет ағашының» бөлу коэффициентіне бөліңіз, яғни беттер / 2. Парақ ішінде дұрыс жылжуды алу үшін, ол ата-ана парағындағы парақ түйіндерінің бірі болуы керек деп есептеңіз, сондықтан офсеттен бастаңыз беттер / 2. Содан кейін ағымдағы бет нөмірі мен ата-ананың бет нөмірі арасындағы айырмашылықты қосыңыз, ата-ана парағынан кейінгі бірінші беттен бастап минус біреуін алып тастаңыз, оның ата-аналық түйіні индексте (беттер / 2).

2 және 3 түйіндер үшін ата-ана режимге байланысты әр түрлі болады. Ғарышты үнемдеу режимінде ата-аналар сәйкесінше 0 және 1 түйіндері болып табылады, сондықтан оларды тек 2-мен алып тастау керек, екінші жағынан, қатаң екілік-ағаш режимінде бұл түйіндер оның орнына парақтың түбірі болып табылады 0 және 1, сондықтан олардың жалпы ата-анасы жоғарыда сипатталғандай есептеледі.

Барлық басқа түйіндер үшін олардың ата-аналары бір парақта болады және олардың парағының орнын парақтың нөмірін өзгертпестен 2-ге бөлу жеткілікті.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Камп, Пул-Хеннинг (2020-07-26). «Сіз мұны дұрыс істемейсіз». ACM кезегі.
  2. ^ Наор, Далит; Мартель, Чарльз У .; Матлофф, Норман С. (1991). «Виртуалды жад ортасында кезек күту құрылымдарының өнімділігі». Есептеу. Дж. 34 (5): 428–437. дои:10.1093 / comjnl / 34.5.428.
  3. ^ ван Эмде Боас, П.; Каас, Р .; Zijlstra, E. (1976). «Тиімді басымды кезекті жобалау және енгізу». Математикалық жүйелер теориясы. 10: 99–127. дои:10.1007 / BF01683268.
  4. ^ phk.freebsd.dk http://phk.freebsd.dk/B-Heap/. Алынған 2019-06-08. Жоқ немесе бос | тақырып = (Көмектесіңдер)

Сыртқы сілтемелер