LSM-дерево

LSM-дерево (от Log-structured merge-tree — журнально-структурированное дерево со слиянием) — используемая во многих СУБД структура данных, предоставляющая быстрый доступ по индексу в условиях частых запросов на вставку (например, при хранении журналов транзакций). LSM-деревья, как и другие деревья, хранят пары «ключ — значение». LSM-дерево поддерживает две или более различные структуры, каждая из которых оптимизирована под устройство, в котором она будет храниться. Синхронизация между этими структурами происходит блоками.

Принцип работы

Простая версия LSM-дерева — двухуровневое дерево — состоит из двух древоподобных структур C0 и C1. C0 меньше по размеру и хранится целиком в оперативной памяти, а C1 находится в энергонезависимой памяти. Новые записи вставляются в C0. Если после вставки размер C0 превышает некоторое заданное пороговое значение, непрерывный сегмент удаляется из C0 и сливается с C1 на устройстве постоянного хранения. Хорошая производительность достигается за счёт того, что деревья оптимизированы под своё хранилище, а слияние осуществляется эффективно и группами по нескольку записей, используя алгоритм, напоминающий сортировку слиянием.

Большинство LSM-деревьев, используемых на практике, реализует несколько уровней. Уровень 0 (назовём его MemTable) хранится в оперативной памяти и может быть представлен обычным деревом. Данные на устройствах постоянного хранения хранятся в виде отсортированных по ключу таблиц (SSTable). Таблица может храниться в виде отдельного файла или набора файлов с непересекающимися значениями ключей. Для поиска конкретного ключа нужно проверить его наличие в MemTable, а затем — пройти по всем SSTable на устройстве постоянного хранения.

Схема работы с LSM-деревом:

  • индексы SSTable всегда загружены в оперативную память;
  • запись производится в MemTable;
  • при чтении сначала проверяется MemTable, а затем, если надо, — SSTable на устройстве постоянного хранения;
  • периодически MemTable сбрасывается в энергонезависимую память для постоянного хранения в виде SSTable;
  • периодически SSTable на устройствах постоянного хранения сливаются.

Искомый ключ может появиться сразу в нескольких таблицах на устройствах постоянного хранения, и итоговый ответ зависит от программы. Большинству приложений нужно лишь последнее значение, относящееся к данному ключу. Другие, например Apache Cassandra, в которой каждое значение представляет собой строку базы данных (а строка может иметь разное количество столбцов в разных таблицах с устройств постоянного хранения), вынуждены как-либо обрабатывать все имеющиеся значения, чтобы получить корректный результат[1]. Чтобы сократить время выполнения запросов, на практике стараются избегать ситуации со слишком большим количеством таблиц на устройствах постоянного хранения.

Были разработаны расширения к «уровневому» методу для поддержания B+‍-структур, например, bLSM[2] и Diff-Index.[3]

Время работы

Архитектура LSM-дерева позволяет удовлетворить запрос на чтение либо из оперативной памяти, либо за одно обращение к устройствам постоянного хранения. Запись тоже всегда быстра независимо от размеров хранилища.

SSTable на устройствах постоянного хранения неизменяема. Поэтому изменения хранятся в MemTable, а удаления должны добавлять в MemTable специальное значение. Поскольку новые считывания происходят последовательно по индексу, обновлённое значение или запись об удалении значения встретятся раньше, чем старые значения. Периодически запускаемое слияние старых SSTable на устройстве постоянного хранения будет производить эти изменения и действительно удалять и обновлять значения, избавляясь от ненужных данных.

Примечания

  1. ↑ Leveled Compaction in Apache Cassandra / datastax.com
  2. ↑ Margo Seltzer | MARGO I. SELTZER is the Canada 150 Research Chair in Computer Science at the University of British Columbia. Her research interests are in systems, construed q... Дата обращения: 5 ноября 2016. Архивировано 3 января 2017 года.
  3. ↑ Архивированная копия. Дата обращения: 5 ноября 2016. Архивировано 3 августа 2016 года.

Ссылки

Read other articles:

نادي اتحاد كلباء

نادي اتحاد كلباء شعار نادي اتحاد كلباء الاسم الكامل نادي اتحاد كلباء الرياضي الثقافي تأسس عام 1971 الملعب استاد نادي اتحاد كلباء الشارقة، الإمارات(السعة: 8,500) البلد الإمارات العربية المتحدة  الدوري دوري أدنوك للمحترفين الإدارة المدرب فرهاد مجيدي الموقع الرسمي الموقع الر...

 

 

Mayotte

Mayottedipartimento d'oltremare (dettagli) (dettagli) Mayotte – VedutaMamoudzou LocalizzazioneStato Francia    Mayotte RegioneNon presente AmministrazioneCapoluogoMamoudzou Amministratore localeBen Issa Ousseni (LR) dal 1-7-2021 TerritorioCoordinatedel capoluogo12°46′44″S 45°13′53.44″E / 12.77889°S 45.23151°E-12.77889; 45.23151 (Mayotte)Coordinate: 12°46′44″S 45°13′53.44″E / 12.77889°S 45.23151°E...

 

 

Baia di Chesapeake

Baia di ChesapeakeLe baie di Chesapeake, in basso, e del Delaware, in alto (foto Landsat).Parte diOceano Atlantico Stato Stati Uniti Stato federato Maryland Virginia Coordinate37°14′53.02″N 76°07′09.98″W / 37.248061°N 76.119439°W37.248061; -76.119439Coordinate: 37°14′53.02″N 76°07′09.98″W / 37.248061°N 76.119439°W37.248061; -76.119439 DimensioniSuperficie11.601 km² Lunghezza330 km Larghezza50 km Profondità...

Alex McMurtry

American artistic gymnast Alex McMurtryFull nameAlexandra Claire McMurtryRegions represented7Born (1996-12-08) December 8, 1996 (age 27)[1]Brighton, Michigan, U.S.HometownMidlothian, Virginia, U.S.Height5 ft 3 in (160 cm)DisciplineWomen's artistic gymnasticsLevelLevel 10ClubRichmond Olympiad GymnasticsCollege teamFlorida Gators (2015–18)Former coach(es)Boris and Larissa ChoutkinRetiredMay 30, 2018 Medal record Representing Richmond Olympiad Nastia ...

 

 

National Aeronautics and Space Act

1958 U.S. law creating NASA National Aeronautics and Space Act of 1958Other short titlesThe Space Act of 1958Long titleAn Act to provide for research into problems of flight within and outside the earth's atmosphere, and for other purposes.Acronyms (colloquial)NASAEnacted bythe 85th United States CongressEffectiveJuly 29, 1958CitationsPublic law85-568Statutes at Large72 Stat. 426-2CodificationTitles amended42 U.S.C.: Public Health and Social WelfareU.S.C. sections created42 U.S...

 

 

Pengolahan air limbah pertanian

Pertanian Umum Agribisnis Agroindustri Agronomi Ilmu pertanian Jelajah bebas Kebijakan pertanian Lahan usaha tani Mekanisasi pertanian Menteri Pertanian Perguruan tinggi pertanian Perguruan tinggi pertanian di Indonesia Permakultur Pertanian bebas ternak Pertanian berkelanjutan Pertanian ekstensif Pertanian intensif Pertanian organik Pertanian urban Peternakan Peternakan pabrik Wanatani Sejarah Sejarah pertanian Sejarah pertanian organik Revolusi pertanian Arab Revolusi pertanian Inggris Revo...

Abstinence-only sex education

Form of sex education Laura Bush with an AIDS orphan at a center in Zambia that promotes abstinence and faith for youth Abstinence-only sex education (also known as sexual risk avoidance education)[1] is a form of sex education that teaches not having sex outside of marriage. It often excludes other types of sexual and reproductive health education, such as birth control and safe sex. In contrast, comprehensive sex education covers the use of birth control and sexual abstinence. Evide...

 

 

Oskari Vuorivirta

This article relies largely or entirely on a single source. Please help improve this article by introducing citations to additional sources.Find sources: Oskari Vuorivirta – news · newspapers · books · scholar · JSTOR (October 2023) Finnish Lutheran pastor and politician (1861–1923) Oskar (Oskari) Herman Vuorivirta (15 January 1861 – 22 December 1923; surname until 1906 Bergström) was a Finnish Lutheran pastor and politician, born in Sotkamo. ...

 

 

Traves (komune)

Traves komune di Italia Tempat Negara berdaulatItaliaDaerah di ItaliaPiemonteKota metropolitan di ItaliaKota Metropolitan Turin NegaraItalia Ibu kotaTraves PendudukTotal503  (2023 )GeografiLuas wilayah10,45 km² [convert: unit tak dikenal]Ketinggian628 m Berbatasan denganGermagnano Mezzenile Viù Pessinetto Informasi tambahanKode pos10070 Zona waktuUTC+1 UTC+2 Kode telepon0123 ID ISTAT001279 Kode kadaster ItaliaL340 Lain-lainSitus webLaman resmi Traves adalah komune yang terletak di...

Damian McBride

Former civil servant and special adviser Damian McBrideDowning Street Press SecretaryIn office2007–2009Prime MinisterGordon BrownPreceded byTom KellySucceeded byGabby Bertin Personal detailsBorn1974 (age 49–50)London, EnglandPolitical partyLabourEducationFinchley Catholic High SchoolAlma materPeterhouse, CambridgeOccupationCivil servant, school business liaison officer Damian McBride (born 1974) is a British political advisor. He is a former Whitehall civil servant and former spe...

 

 

Smith Commission

Cameron-era government body on Scottish devolution Lord Smith of Kelvin holding the Commission's report The Smith Commission was announced by Prime Minister David Cameron on 19 September 2014 in the wake of the 'No' vote in the 2014 Scottish independence referendum. The establishment of the commission was part of the process of fulfilling The Vow made by the leaders of the three main unionist parties during the last days of the referendum campaign. The Vow promised the devolution of more powe...

 

 

Public domain (land)

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) The examples and perspective in this article deal primarily with the United States and do not represent a worldwide view of the subject. You may improve this article, discuss the issue on the talk page, or create a new article, as appropriate. (December 2018) (Learn how and when to remove this message) This article needs additional citations...

Ranking

Relationship between items in a set Rankings, Ranked, and Second place redirect here. For other uses, see List of international rankings, Ranked (musical), Ranking (surname), Rank (disambiguation), and Second Place (disambiguation). This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Ranking – news · newspapers · books ...

 

 

Angul (raja)

Menurut Saxo Grammaticus dalam bukunya berjudul scholium, Dan dan Angul (Angel) bersaudaraan. Uppsala Kuno, tempat Angul dan Dan mungkin dibesarkan. (Uppsala hov, dilukis oleh Carl Johan Billmark) Angul (juga dikenal sebagai Angull atau Angel) adalah leluhur Angli, suku yang berasal dari Jutlandia (sekarang Denmark), menurut Gesta Danorum,. Ayahnya bernama Humbli, mungkin merupakan orang yang sama dengan Heimdallr. Tradisi Nordik Getica (Goth) Menurut catatan berjudul Getica yang ditulis oleh...

 

 

History of Wrigley Field

History of the baseball stadium in Chicago, Illinois The history of Wrigley Field, the home of the Chicago Cubs of Major League Baseball's National League, begins well before the Cubs played their first game in that venue. Before the Federal League Chicago Lutheran Theological Seminary, seen around 1900, from Sheffield Avenue. The president's house on the right is located near the site of the present-day Wrigley Field scoreboard and center field bleachers. The building in the center, Eliza Ha...

Thomas Blow

Canadian politician Thomas Henry BlowThomas Blow 1913 campaign photoMember of the Legislative Assembly of AlbertaIn officeApril 17, 1913 – July 17, 1921ConstituencySouth Calgary Personal detailsBorn(1862-01-22)January 22, 1862North Mountain, Canada WestDiedDecember 27, 1932(1932-12-27) (aged 70)Vancouver, British ColumbiaPolitical partyConservativeSpouseIda J.Children4Alma materMcGill University (M.D.)Occupationdoctor Thomas Henry Blow (January 22, 1862 – December 27, 1932) ...

 

 

Oliver Campbell

American tennis player (1871–1953) Oliver CampbellFull nameOliver Samuel Edward Michael CampbellCountry (sports) United StatesBorn(1871-02-25)February 25, 1871Brooklyn, NY, U.S.DiedJuly 11, 1953(1953-07-11) (aged 82)Campbellton, New Brunswick, CanadaTurned pro1886 (amateur tour)Retired1892Int. Tennis HoF1955 (member page)SinglesCareer titles17Highest rankingNo. 8 (1890, ITHF)[1]Grand Slam singles resultsWimbledon2R (1892)US OpenW (1890, 1891, 1892)...

 

 

Jesse Harper

Jesse HarperBiographical detailsBorn(1883-12-10)December 10, 1883Paw Paw, Illinois, U.S.DiedJuly 31, 1961(1961-07-31) (aged 77)Sitka, Kansas, U.S.Playing careerFootball1905ChicagoBaseball1903–1906Chicago Coaching career (HC unless noted)Football1906–1907Alma1909–1912Wabash1913–1917Notre DameBasketball1910–1913Wabash1913–1918Notre DameBaseball1910–1913Wabash1914–1918Notre Dame Administrative career (AD unless noted)1913–1917Notre Dame1931–1933Notre Dame Head coaching ...

Praetorian prefect

High office in the Roman Empire Part of a series on theMilitary of ancient Rome 753 BC – AD 476 Structural history Army Unit types and ranks Decorations and punishments Legions Auxilia Generals Navy Fleets Admirals Campaign history Wars and battles Technological history Military engineering Castra Siege engines Triumphal arches Roads Political history  Strategy and tactics Infantry tactics Frontiers and fortifications Limes Walls Limes Britannicus Antonine Wall Hadrian's Wall Saxon Sho...

 

 

الخطوط التونسية السريعة

  ميّز عن الخطوط التونسية. طيران السابع   إياتاUG إيكاوTUI رمز النداءSevenair تاريخ الإنشاء 1991 الجنسية تونس  المطارات الرئيسية مطار تونس قرطاج الدولي حجم الأسطول 4 الوجهات 18 الشركة الأم الخطوط التونسية المقرات الرئيسية تونس العاصمة،  تونس موقع ويب www.tunisairexpress.com تعديل...