R-strom (anglicky R-tree) je stromová datová struktura podobná B-stromům, ale používaná pro prostorové přístupové metody, například pro indexovaní vícerozměrných struktur například v geografických informačních systémech. Mimo to, pomocí R-stromů je implementováno například datové úložiště MyISAM v MySQL.Datová struktura dělí místo na hierarchicky vkládané a potenciálně se překrývající, tzv.
| Property | Value |
|---|
| prop-cs:wikiPageUsesTemplate
| |
| dbpedia-owl:abstract
|
- R-strom (anglicky R-tree) je stromová datová struktura podobná B-stromům, ale používaná pro prostorové přístupové metody, například pro indexovaní vícerozměrných struktur například v geografických informačních systémech. Mimo to, pomocí R-stromů je implementováno například datové úložiště MyISAM v MySQL.Datová struktura dělí místo na hierarchicky vkládané a potenciálně se překrývající, tzv. MBR (minimum bounding rectangles – minimální ohraničující obdélníky, též nazývané obdélníky nebo boxy – R z anglického výrazu pro obdélník (rectangle) tvoří část názvu R-stromů).Každý uzel R-stromu má proměnlivý počet záznamů (až do předdefinovaného maxima). Každý záznam uvnitř uzlu, který není listem, ukládá dvě další informace: způsob identifikace dceřiného uzlu a MBR všech záznamů uvnitř tohoto dceřiného uzlu.Algoritmy pro vložení nového a smazání stávajícího prvku používají MBR z uzlů ke kontrole, že prvky v geometrickém okolí jsou umístěny do stejných listových uzlů (konkrétně, nový prvek půjde do listového uzlu, který potřebuje nejmenší rozšíření svého MBR). Každý záznam uvnitř listového uzlu uloží dvě informace: identifikátor daného prvku (který může být alternativně umístěn přímo do uzlu) a MBR datového prvku.Podobně, vyhledávací algoritmy používají MBR k rozhodnutí, zdali hledat uvnitř daného uzlu. Tímto způsobem při hledání většina uzlů „netknutých“. Stejně jako B-stromy, jsou R-stromy vhodné pro databáze, kde se uzly podle potřeby mohou načítat do paměti.U R-stromů lze nastavit nejen maximální počet prvků v něm, ale i algoritmus, kdy se má daný list změnit v uzel další úrovně. Mezi tyto algoritmy patří: linear-cost algoritm quadratic-cost algoritm exhaustive algoritmR-stromy nezaručují dobrý výkon pro nejnepříznivější případ uložení dat, ale jejich implementace dosahují slušných výkonů při použití „reálných“ dat. V roce 2004 byl nicméně vyvinut nový algoritmus, Priority R-Tree, který má výkon vylepšovat právě pro nepříznivě uložená data.
|
| dbpedia-owl:thumbnail
| |
| dbpedia-owl:wikiPageExternalLink
| |
| dbpedia-owl:wikiPageID
| |
| dbpedia-owl:wikiPageLength
| |
| dbpedia-owl:wikiPageOutDegree
| |
| dbpedia-owl:wikiPageRevisionID
| |
| dbpedia-owl:wikiPageWikiLink
| |
| dbpedia-owl:wikiPageWikiLinkText
| |
| dcterms:subject
| |
| rdfs:comment
|
- R-strom (anglicky R-tree) je stromová datová struktura podobná B-stromům, ale používaná pro prostorové přístupové metody, například pro indexovaní vícerozměrných struktur například v geografických informačních systémech. Mimo to, pomocí R-stromů je implementováno například datové úložiště MyISAM v MySQL.Datová struktura dělí místo na hierarchicky vkládané a potenciálně se překrývající, tzv.
|
| rdfs:label
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbpedia-owl:wikiPageRedirects
of | |
| is dbpedia-owl:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
