R+ ағашы: географиялық деректерді (координаттар) іздеу үшін қолданылатын кеңейтілген дерек құрылымы. R ағаштары мен kd ағаштарының артықшылықтарын біріктіреді.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
R+ ағашы – координаталар (көбінесе x, y) немесе Жер бетіндегі орналасқан жерлерді пайдаланып деректерді іздеу әдісі. Бір сан бойынша іздеу мәселесі шешілген, бірақ екі немесе одан көп сандар бойынша іздеу және x және y бағыттарындағы жақын жерлерді табу үшін күрделірек алгоритмдер қажет. Негізінде, R+ ағашы – кеңістіктік ақпаратты индекстеуге арналған R ағашының бір түрі, деректер құрылымы.
An R+ tree is a method for looking up data using a location, often (x, y) coordinates, and often for locations on the surface of the Earth. Searching on one number is a solved problem; searching on two or more, and asking for locations that are nearby in both x and y directions, requires craftier algorithms. Fundamentally, an R+ tree is a tree data structure, a variant of the R tree, used for indexing spatial information.
R + және R ағаштары арасындағы айырмашылық
R+ ағаштары – R ағаштары мен kd ағаштары арасындағы шартты келісім: қажет болған жағдайда бір нысанды бірнеше жапыраққа орналастыру арқылы ішкі түйіндердің араласуына жол бермейді. Қамту – бұл барлық байланысты тіктөртбұрыштарды қамтитын жалпы аумақ. Араласу – екі немесе одан көп түйіндерде орналасқан аумақ. Минималды қамту R ағашы түйіндерімен жабылатын "бос кеңістіктің" (бос аймақтың) көлемін азайтады. Минималды араласу жапырақтарға дейінгі іздеу жолдарының санын азайтады (бұл қолжетімділік уақыты үшін минималды қамтудан да маңыздырақ). Тиімді іздеу үшін минималды қамту және араласу қажет. R+ ағаштары R ағаштарынан мынадай ерекшеліктерімен айырылады: түйіндердің кемінде жартысы толтырылғанына кепілдік жоқ, кез келген ішкі түйіндегі жазбалар араласпайды және нысан ID бірнеше жапырақ түйінінде сақталуы мүмкін.
R+ trees are a compromise between R trees and kd trees: they avoid overlapping of internal nodes by inserting an object into multiple leaves if necessary. Coverage is the entire area to cover all related rectangles. Overlap is the entire area which is contained in two or more nodes. Minimal coverage reduces the amount of "dead space" (empty area) which is covered by the nodes of the R tree. Minimal overlap reduces the set of search paths to the leaves (even more critical for the access time than minimal coverage). Efficient search requires minimal coverage and overlap. R+ trees differ from R trees in that: nodes are not guaranteed to be at least half filled, the entries of any internal node do not overlap, and an object ID may be stored in more than one leaf node.
Артықшылықтар
Түйіндер бір-бірімен қабаттаспағандықтан, нүктелік сұраныстың жылдамдығы артады, себебі барлық кеңістіктік аймақтар ең көп дегенде бір түйінмен ғана қамтылады. Бір жолмен өтіліп, R-ағашына қарағанда аз түйіндер қарастырылады.
Because nodes are not overlapped with each other, point query performance benefits since all spatial regions are covered by at most one node. A single path is followed and fewer nodes are visited than with the R tree.
Кемшіліктер
Тікбұрыштар көшірілгендіктен, бірдей деректер жиынтығында салынған R ағашына қарағанда R+ ағашы үлкен болуы мүмкін. R+ ағаштарын құру және күтіп ұстау, R ағаштарын және R ағашының басқа түрлерін құру мен күтіп ұстауға қарағанда күрделірек.
Since rectangles are duplicated, an R+ tree can be larger than an R tree built on same data set. Construction and maintenance of R+ trees is more complex than the construction and maintenance of R trees and other variants of the R tree.