Redigerer Btrfs (avsnitt)

===B-trær i forbindelse med btrfs===
Datatrukturen ble beskrevet i forbindelse med filsystemer av Ohad Roed, en forsker ved [[IBM]], under konferansen til [[USENIX]] i juni 2007.<ref name="USENIX"/> I sitt opprinnelige forslag drøftet Rodeh B+ trær, som er i utbredt bruk som [[datastruktur]]er i [[database]]r.{{#tag:ref|Blant [[databaser]] som bruker B+ trær kan nevnes: [[IBM DB2]],<ref name="Ramakrishnan2002"/> [[IBM Informix]],<ref name="Ramakrishnan2002"/> [[Microsoft SQL Server]],<ref name="Ramakrishnan2002"/> [[Oracle Database]],<ref name="Ramakrishnan2002"/> [[Adaptive Server Enterprise|Sybase ASE]]<ref name="Ramakrishnan2002"/> og [[SQLite]].<ref>[http://sqlite.org/version3.html SQLite Version 3 Overview], sqlite.org, 2004</ref>|group="lower-alpha"|name="databaser"}} Rohed påpekte at B+ trær ikke kunne tillate [[copy-on-write]] baserte [[Snapshot (datalagring)|snapshots]] på en effektiv måte. Årsaken er at løvnodene er lenket sammen: Hvis en løvnode blir kopiert på denne måten, vil dens søsken og foreldre også bli kopiert, såvel som ''deres'' søsken og foreldre, og så videre inntil hele treet er kopiert. 
[[Fil:Oracle Redwood City May 2011 001.jpg|thumb|Hovedkvarteret til [[Oracle (selskap)|Oracle Corporation]] bygning 300, i Redwood Shores, Redwood City, [[California]]. Chris Mason, som var den opprinnelige arkitekten til btrfs, var ansatt av Oracle Corporation.{{byline|Foto:King of Hearts|7. mai 2011}}]]
I stedet foreslo han et modifisert B-tre uten noen sammenlenkede løv, med en [[referansetelling|referanseteller]] tilknyttet hver node i treet, lagret i en [[ad-hoc]] [[assosiativ tabell]]struktur, og med visse kompromisser relatert til treets algoritmer for belastningsfordeling for å gjøre dem copy-on-write vennlige. Resultatet ville bli en datastruktur som var egnet for høyytelses objektlagring som kunne utføre copy-on-write snapshots samtidig som de utførte [[parallelle beregninger]] på en god måte.<ref name="USENIX"/>

I juli samme år ble ingeniøren Chris Mason ansatt hos [[Oracle Corporation]] og begynte å arbeide på et nytt filsystem med muligheter for snapshots basert på B-trær.<ref name="Marabel"/> Dette var begynnelsen på btrfs. Han hadde tidligere arbeidet med det journalførende filsystemet ReiserFS for SuSE.<ref name="Interview"/> Han arbeidet ikke bare med [[metadata]] og fildata, men også [[rekursjon|rekursivt]] for å finne plass til å allokere treene selv. Dette gjorde at all traversering og alle modifikasjoner kunne utføres i en enkelt kode, noe som gjorde at copy-on-write, [[sjekksum]]mer og speiling bare behøvde å implementeres en gang for å dra nytte av hele filsystemet.<ref name="Aurora">Valerie Aurora: [https://lwn.net/Articles/342892/ A short history of btrfs], LWN.net, 2009</ref>

Btrfs er strukturert i form av flere lag av slike trær, som alle bruker den samme B-tre implementasjonen. Trærne lagrer generiske ''elementer'', som er sortert med en 136-biter nøkkel. De første 64 bitene av nøkkelen er en unik ''objekt-id''. De midterste 8 bitene er et elementtypefelt, det er hardkodet som et elementfilter under oppslag i treet. ''Objekter'' kan ha flere elementer av flere datatyper. De resterende 64-biter benyttes på typespesifikke måter. Elementer for det samme objektet ender derfor opp som naboer til hverandre i treet, ordnet etter type. Ved å velge visse nøkkelverdier som er satt sammen av de resterende 64-biter, kan objekter videre plassere elementer av samme type i en spesiell rekkefølge.<ref name="Aurora"/><ref name="btrfs-wiki-1">[https://btrfs.wiki.kernel.org/index.php/Main_Page Btrfs Main Page], btrfs.wiki.kernel.org, 5. oktober 2016</ref>

Innvendige trenoder er kort og godt flate lister av nøkkelpeker-par, hvor pekeren er antallet logiske  blokker til en barnenode. Løvnoder inneholder elementnøkler som er pakket inn i fronten av noden og elementdata pakket inn på slutten, med to som vokser mot hverandre ettersom løvet fylles opp.<ref name="Aurora"/>