R-strom

Schéma R-stromů na jednoduchém příkladu.

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 algoritm

R-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.

Varianty

  • R* strom
  • R+ strom
  • Hilbertův R-strom
  • Prioritní R-strom (PR-strom)

Odkazy

Reference

V tomto článku byl použit překlad textu z článku R-tree na anglické Wikipedii.

Literatura

Externí odkazy

Pahýl
Pahýl
 Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.
Stromové datové struktury
Vyhledávací stromy
(dynamické množiny/ asociativní pole)

2–3 • 2–3–4 • AA • (a,b) • AVL • B • B+ • B* • Bx • (Optimální) Binární vyhledávací • Dancing • HTree • Intervalový • Stromy s pořadím (Order statistic) • (Doleva převážený) Červeno-černý • Scapegoat • Splay • T • Treap • UB • Váhově vyvážený (tj. BB[α])

Haldy
Trie

Ctrie • C-trie • Hašovací • Komprimovaná trie (tj. Patricia) • Sufixový (tj. PAT) • Ternální hledání • X-fast • Y-fast

Prostorové indexační stromy

Ball • BK • BSP • Kartézský • Hilbertův R • k-d (implicitní k-d) • M • Metrický • MVP • Oktálový (Octree) • PH • Prioritní R • Čtyřstrom (Quadtree) • R • R+ • R* • Segmentový • VP (vantage-point) • X

Jiné stromy

Strom pokrytí • Obousměrně provázaný (Doubly chained tree) • Exponenciální • Fenwickův • (Binární) Strom s prstem • Fraktálový indexový • Fúzní (Fusion tree) • Hašovací kalendář • iDistance • K-ární • Knuthův transformovaný (Left-child right-sibling binary tree) • Link/cut • Log-strukturovaný spojovací • Hašový Merkleův (TTH) • PQ • Rozsahový (Range) • SPQR • Top (Horní strom)

Kategorie:Stromy (dat. strukt.)

Read other articles:

Curug Cileat

Curug CileatLokasiDesa Mayang, Kecamatan Cisalak, Kabupaten Subang, Provinsi Jawa Barat, IndonesiaKoordinat6°46′51.5″S 107°45′04.09″E / 6.780972°S 107.7511361°E / -6.780972; 107.7511361Koordinat: 6°46′51.5″S 107°45′04.09″E / 6.780972°S 107.7511361°E / -6.780972; 107.7511361TipePlungeTinggi total100 meter (328 ft)Jumlah titik1 (Satu)Anak sungaiSungai Cipunagara Curug Cileat adalah sebuah curug atau air terjun yang ter...

 

Annabelle Wallis

Annabelle WallisWallis pada tahun 2017LahirAnnabelle Frances Wallis5 September 1984 (umur 39)Oxford, Oxfordshire, InggrisNama lainAnnabelle WallacePekerjaanAktrisTahun aktif2005–sekarang Annabelle Frances Wallis (lahir 5 September 1984) adalah seorang aktris asal Inggris. Ia dikenal karena memerankan Jane Seymour dalam drama periode Showtime, The Tudors (2009-2010), Grace Burgess dalam drama BBC, Peaky Blinders (2013-2019), Mia dalam film horor supranatural, Annabelle (2014)...

 

The Conqueror (1917 film)

1917 film The ConquerorAdvertisementDirected byRaoul WalshScreenplay byChester B. ClappRaoul WalshStory byHenry Christeen WarnackProduced byWilliam FoxStarringWilliam FarnumCinematographyDel ClawsonDistributed byFox Film CorporationRelease date September 16, 1917 (1917-09-16) Running time80 minutesCountryUnited StatesLanguagesSilentEnglish intertitles The Conqueror is a 1917 American silent biographical Western film directed by Raoul Walsh and starring William Farnum. It was pr...

November 1933

Month of 1933 1933 January February March April May June July August September October November December << November 1933 >> Su Mo Tu We Th Fr Sa 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30   November 16, 1933: Jimmy Angel discovers Angel Falls in Venezuela November 11, 1933: Williamson-Balfour Company turns Easter Island over to ChileNovember 11, 1933: Dust Bowl storms begin in the United States The following events occurred in N...

 

Jeffrey Ashby

Jeffrey S. AshbyLahirJeffrey Shears Ashby16 Juni 1954 (umur 69)Dallas, Texas, Amerika SerikatStatusDipekerjakan oleh Blue OriginKebangsaanAmerika SerikatAlmamaterUniversitas Idaho, Sarjana 1976Universitas Tennessee, Magistrat 1993PekerjaanPenerbang angkatan laut, pilot uji cobaPenghargaan Karier luar angkasaAntariksawan NASAPangkatKapten Angkatan Laut Amerika SerikatWaktu di luar angkasa27 hari 16 jam 19 menitSeleksi1994 NASA Group 15MisiSTS-93, STS-100, STS-112Lambang misi PensiunJuni ...

 

2020 Arizona Democratic presidential primary

State election for the 2020 Democratic National Convention 2020 Arizona Democratic presidential primary ← 2016 March 17, 2020 2024 → ← MPFL →80 delegates (67 pledged, 13 unpledged)to the Democratic National ConventionThe number of pledged delegates won is determined by the popular vote   Candidate Joe Biden Bernie Sanders Home state Delaware Vermont Delegate count 38 29 Popular vote 268,029 200,456 Percentage 43.7% 32.7%   C...

Robert Badinter

French lawyer, politician and author (1928–2024) Robert BadinterBadinter in 2013SenatorIn office24 September 1995 – 30 September 2011Preceded byFrançoise SeligmannSucceeded byPhilippe KaltenbachConstituencyHauts-de-SeinePresident of the Constitutional CouncilIn office4 March 1986 – 4 March 1995Appointed byFrançois MitterrandPreceded byDaniel MayerSucceeded byRoland DumasMinister of JusticeIn office23 June 1981 – 19 February 1986PresidentFrançois Mitterran...

 

Muhammad Shah II di Terengganu

Muhammad Shah II di TerengganuIl sultano in gioventù.Sultano di TerengganuIn carica26 novembre 1918 –20 maggio 1920 PredecessoreZainal Abidin III SuccessoreSulaiman Badrul Alam Shah Nome completoPaduka Sri Tuanku Sultan Haji Muhammad II Muazzam Shah ibni al-Marhum Sultan Zainal Abidin NascitaKuala Terengganu, 7 settembre 1888 MorteIstana Gong Kapas, Kuala Terengganu, 11 aprile 1956 (67 anni) Luogo di sepolturaMoschea Zainal Abidin, Kuala Terengganu PadreZainal Abidin III di...

 

Amblar-Don

Cet article est une ébauche concernant le Trentin-Haut-Adige. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Amblar-Don Administration Pays Italie Code postal 38011 Préfixe tel. 0463 Démographie Population 543 hab. (1er janvier 2023[1]) Densité 28 hab./km2 Géographie Coordonnées 46° 24′ nord, 11° 09′ est Superficie 1 906 ha = 19,06 km2 Localisat...

Living history

Historical reenactment This article is about the term as it applies to historical reenactors. For Hillary Clinton's autobiography, see Living History (book). A reenactress playing the role of Mary Queen of Scots at a Scottish fair in 2003. Living history is an activity that incorporates historical tools, activities and dress into an interactive presentation that seeks to give observers and participants a sense of stepping back in time. Although it does not necessarily seek to reenact a specif...

 

Colin Smyth

Scottish Labour politician Colin SmythMSPSmyth in 2017Member of the Scottish Parliamentfor South Scotland(1 of 7 Regional MSPs)IncumbentAssumed office 6 May 2016Scottish Labour portfolios2017–2021Shadow Cabinet Secretary for Transport, Infrastructure and Connectivity2021–presentShadow Cabinet Secretary for Constitution, Europe and External Affairs Personal detailsBornNovember 1972 (age 51)Dumfries, ScotlandPolitical partyScottish LabourAlma materUniversity of GlasgowWebsiteO...

 

巴育·占奥差

將軍巴育·占奥差ประยุทธ์ จันทร์โอชา上將 MPCh MWM TChW 泰國樞密院議員现任就任日期2023年11月29日君主拉瑪十世議長素拉育·朱拉暖 泰國第29任總理任期2022年9月30日復職—2023年8月22日君主拉瑪十世副總理（英语：Deputy Minister of Thailand） 列表 巴威·翁素万塔那塞·巴滴玛巴功（英语：Thanasak Patimaprakorn） 威沙努·革岸（英语：Wissanu Krea-ngam） 比蒂耶�...

Венгер, Леонид Абрамович

В Википедии есть статьи о других людях с такой фамилией, см. Венгер. Леонид Абрамович Венгер Дата рождения 26 мая 1925(1925-05-26) Место рождения Харьков Дата смерти 17 июня 1992(1992-06-17) (67 лет) Место смерти Москва Страна  СССР Род деятельности психолог Научная сфера возраст�...

 

Adobe Inc.

American multinational software company Adobe, Inc.Adobe World Headquarters in San Jose, CaliforniaFormerlyAdobe Systems Incorporated (1982–2018)Company typePublicTraded asNasdaq: ADBENasdaq-100 componentS&P 100 componentS&P 500 componentIndustrySoftwareFoundedDecember 1982; 41 years ago (1982-12)Mountain View, California, U.S.FoundersJohn WarnockCharles GeschkeHeadquartersAdobe World Headquarters, San Jose, California, U.S.Area servedWorldwideKey peopleS...

 

Tuscia

Historical region of Italy You can help expand this article with text translated from the corresponding article in Italian. (March 2023) Click [show] for important translation instructions. View a machine-translated version of the Italian article. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated t...

江崎孝

本来の表記は「江﨑孝」です。この記事に付けられたページ名は技術的な制限または記事名の制約により不正確なものとなっています。 日本の政治家江﨑 孝えさき たかし 2020年10月、立憲民主党福岡県総支部連合会結成時に行われた街頭演説会における江崎生年月日 (1956-08-11) 1956年8月11日（67歳）出生地 福岡県三橋町（現：柳川市）出身校 法政大学社会学部前職 地方�...

 

Stepney

For other uses, see Stepney (disambiguation). Human settlement in EnglandStepneyClockwise from top left: St. Dunstan's Church; Stepney Green tube station; Genesis cinema; route 135 at Arbour Square; Stepney Green; the Half Moon pub.StepneyLocation within Greater LondonPopulation16,238 (2011 census. St Dunstan's and Stepney Green Ward)[1]OS grid referenceTQ355814• Charing Cross3.6 mi (5.8 km) WSWLondon boroughTower HamletsCeremonial county...

 

Diadem

Ornamental headband worn by monarchs and others as a badge of royalty For other uses, see Diadem (disambiguation). Coin of Antiochus III the Great of the Seleucid Empire, shown wearing a diadem; the Greek inscription reads ΒΑΣΙΛΕΩΣ ΑΝΤΙΟΧΟΥ, of King Antiochus. Gold diadem. India, 9th–10th century Diadem given to Veiled Prophet Queen of Love and Beauty, Veiled Prophet Ball, St. Louis, Missouri, in 1920 A diadem is a type of crown, specifically an ornamental headband worn by m...

Reproduksi aseksual

Reproduksi yang dilakukan lumut hati adalah contoh reproduksi aseksual. Reproduksi aseksual atau perkembangbiakan aseksual adalah proses reproduksi pada saat keturunan timbul dari orang tua tunggal, dan mewariskan genetika dari satu orang tua. Aseksual adalah reproduksi yang tidak melibatkan meiosis, ploidi pengurangan, atau fertilisasi. Sebuah definisi yang lebih ketat adalah agamogenesis yang adalah reproduksi tanpa fusi gamet. Reproduksi aseksual adalah bentuk reproduksi organisme bersel t...

 

سنة

  لمعانٍ أخرى، طالع سنة (توضيح). سنةمعلومات عامةالنوع وحدة زمن[1] — وحدة بدون تحويل قياسي إلى وحدة النظام الدولي (SI). — وحدة مشتقة من UCUM لديه جزء شهر جزء من période sothiaque (fr) تستخدم لقياس المدة الزمنية[1] رمز الوحدة  القائمة ... a (بالإنجليزية)[1] год (بالروسية)[2]...