Redigerer Btrfs (avsnitt)

==Oppbygning==
===Journalførende filsystem===
{{utdypende|Journalførende filsystem|ext3|ext4}}
Det er viktig for forståelsen å ikke bare behandle btrfs isolert, men også se på den helhetlige sammenheng som btrfs oppstod innenfor. 
[[Fil:Elivescreenshot.jpeg|thumb|Skjermbilde av [[Linuxdistribusjon]]en [[Elive]]. Elive benyttet filsystemet [[ReiserFS]].{{byline|Foto:Jimmy Robaer|10. juli 2007}}]]
Liksom forgjengerne [[ext3]] og [[ext4]], er btrfs et [[journalførende filsystem]]. Dette betyr at [[filsystem]]et lagrer endringer av [[datafil]]er i en [[journal]], før endringene blir foretatt. Ved systemkrasj og strømbrudd, er slike filsystemer lettere å gjenopprette og mindre sårbare for skader.<ref name="developerworks-1">{{citation|title = Anatomy of Linux journaling file systems|url = http://www.ibm.com/developerworks/library/l-journaling-filesystems/index.html|publisher = IBM DeveloperWorks|date = 2008-06-04|accessdate = 2009-04-13|first = M Tim|last = Jones}}</ref><ref name="ostep-1">{{citation|title=Crash Consistency: FSCK and Journaling|url=http://pages.cs.wisc.edu/~remzi/OSTEP/file-journaling.pdf|publisher = Arpaci-Dusseau Books|date = 2014-01-21|first1 = Remzi H.|last1 = Arpaci-Dusseau|first2=Andrea C.|last2 = Arpaci-Dusseau}}</ref>

[[Linuxkjernen]] inneholder flere slike journalførende filsystemer, som har hatt stor innflytelse på utviklingen av btrfs. Av disse vil vi fremheve [[XFS]], [[ReiserFS]], [[Reiser4]], [[Journaled File System]] (JFS), [[ZFS]] og [[OpenZFS]]:

* XFS er et 64-biter filsystem som ble utviklet av [[Silicon Graphics|Silicon Graphics Inc.]] (SGI) i 1993.<ref name="XFS">[http://xfs.org/docs/xfsdocs-xml-dev/XFS_User_Guide/tmp/en-US/html/ch01s02.html "''xFS: the extension of EFS - "x" for to-be-determined (but the name stuck)''"] {{Wayback|url=http://xfs.org/docs/xfsdocs-xml-dev/XFS_User_Guide/tmp/en-US/html/ch01s02.html |date=20140714224038 }}, xfs.org, XFS User Guide. A guide for XFS filesystem users and administrators. Edition 0, 2006</ref> Det var standard filsystem i [[operativsystem]]et [[IRIX]] fra versjon 5.3 i desember 1994.<ref name="XFS"/> I mai 2001 ble XFS tilføyd Linuxkjernen i form av [[patch]]er fra SGI,<ref>Russel Ingram: [http://www.tldp.org/HOWTO/archived/Linux+XFS-HOWTO/ Linux + XFS HOWTO. Linux on Steroids], tldp.org, 12. mai 2002</ref> før det ble integrert i kjernens versjon 2.6 den 18. desember 2003.{{#tag:ref|[[Gentoo]] var i 2002 den første Linuxdistribusjonen som benyttet XFS som standard;<ref>[http://www.linuxdevcenter.com/pub/a/linux/2002/10/10/intro_gentoo.html?page=2 Gentoo Linux Reloaded], O'Reilly Linux Devcenter, 2016</ref> filsystemet er også standard i [[Red Hat Enterprise Linux]] 7.0<ref name="RHEL7"/> og [[Oracle Linux]] 7.0.<ref name="Oracle Linux 7"/>|group="lower-alpha"|name="xfslinux"}}

* ReiserFS ble utviklet av den amerikanske programmereren [[Hans Reiser]] og ble innlemmet i versjon 2.4.1 av Linuxkjernen den 30. januar 2001.<ref name="diskinternals"/>{{#tag:ref|ReiserFS har vært standard i distribusjonene [[Elive]], [[FTOSX Desktop]],<ref>[https://distrowatch.com/table.php?distribution=ftosx FTOSX Desktop], DistroWatch, 1. juli 2016</ref> [[Xandros]],<ref>N. Heron: [http://www.osnews.com/story/2228 Review of Xandros Desktop 1.0], OSNews.com, 25. november 2002</ref> [[Kurumin]],<ref>[https://distrowatch.com/table.php?distribution=kurumin Kirumin Linux], DistroWatch, 1. juli 2016</ref> [[Libranet]],<ref>[https://distrowatch.com/table.php?distribution=libranet Libranet GNU/Linux], DistroWatch, 1. juli 2016</ref> [[Linspire]],<ref>[https://distrowatch.com/table.php?distribution=linspire Linspire], DistroWatch, 1. juli 2016</ref> [[GoboLinux]],<ref>[https://distrowatch.com/table.php?distribution=gobo GoboLinux], DistroWatch, 10. oktober 2016</ref> [[Slackware]]<ref>[https://distrowatch.com/table.php?distribution=slackware Slackware Linux], DistroWatch, 10. oktober 2016, </ref> og [[YOPER]].<ref>[https://distrowatch.com/table.php?distribution=yoper Yoper Linux], DistroWatch, 1. juli 2016</ref><ref name="diskinternals">[http://www.diskinternals.com/glossary/reiserfs.html ReiserFS], Data Recovery Glossary, DiskInternals, ltd., 2016</ref> ReiserFS var også standard i [[SUSE Linux Enterprise Server]] og [[SUSE Linux Enterprise Desktop]], inntil [[Novell]] den 12. oktober 2006 besluttet seg for å gå over til ext3.<ref>[http://www.liquisearch.com/what_are_reiserfs What are reiserfs?], liquisearch.com</ref>|group="lower-alpha"|name="reiserfslinux"}}

* Hans Reiser utviklet også etterfølgeren Reiser4.<ref>[https://reiser4.wiki.kernel.org/index.php/Future_Vision Future Vision - Reiser4], reiser4.wiki.kernel.org, 25. august 2016</ref> Dette er blitt sponset av forvaltningsorganet [[Defense Advanced Research Projects Agency]] (DARPA)<ref name="reiser4credits">[https://reiser4.wiki.kernel.org/index.php/Credits Credits - Reiser4 FS], reiser4.wiki.kernel.org, 18. november 2009</ref> så vel som av ApplianceWare, BigStorage, Inc., [[SUSE Linux|SuSE]] og Linspire,<ref name="reiser4credits"/> og ble en del av versjon 3.15 av Linuxkjernen den 14. august 2014.

[[Fil:Mandriva 2010.png|thumb|Skjermbilde av [[Mandriva Linux]] 2010. Denne distribusjonen benyttet filsystemet [[Journaled File System]].{{byline|Foto:Xurdus|12. november 2009}}]]
* Journaled File System (JFS) ble utviklet av [[IBM]] og lansert for operativsystemet [[AIX]] i februar 1990.<ref>[https://wiki.archlinux.org/index.php/JFS JFS], wiki.archlinux.org, 30. august 2016</ref> I september 1994 ble det også tatt i bruk i [[OS/2]] 3.0 «Warp».<ref>[https://www.elstel.org/OS2Warp/InstallUpdate.html OS/2 Warp Installation and Update Manual], IBM</ref> En rekke Linuxdistribusjoner støtter eller har støttet JFS.<ref name="jfsnet"/>{{#tag:ref|En rekke Linuxdistribusjoner støtter eller har støttet JFS,<ref name="jfsnet">[http://jfs.sourceforge.net/ JFS for Linux], jfs.sourceforge.net</ref> deriblant [[ALT Linux]], [[Arch Linux]], [[Debian]], Gentoo, [[Knoppix]], [[Mandriva Linux]], Onyx, [[Red Hat Linux]], Slackware, [[SUSE Linux]], [[Turbolinux]] og [[United Linux]],<ref name="jfsnet"/> og det var standard i den tidligere distribusjonen [[Shark Linux]].<ref name="jfsnet"/>|group="lower-alpha"|name="JFS Linux"}}

* ZFS (''Zettabyte File System'') ble utviklet av [[Sun Microsystems]] for operativsystemet [[OpenSolaris]] i 2005.<ref>[https://blogs.oracle.com/bonwick/entry/zfs_the_last_word_in ZFS: The Last Word in Filesystems], Jeff Bonwick's blog, Oracle Corporation, 31. oktober 2005</ref> Det ble i utgangspunktet lisensiert under en [[åpen kildekode]]lisens, men [[Oracle (selskap)|Oracle Corporation]] endret denne i 2010 til en [[proprietær programvare|proprietær lisens]] for operativsystemet [[Solaris (operativsystem)|Solaris]].<ref name="arstechnica">Ryan Paul: [http://arstechnica.com/information-technology/2010/06/uptake-of-native-linux-zfs-port-hampered-by-license-conflict/ Uptake of native Linux ZFS port hampered by license conflict], arstechnica.com, 6. september 2009</ref> Grunnet lisensieringsproblemer er det ikke mulig å videreutvikle ZFS for Linuxkjernen,<ref name="arstechnica"/><ref>Dustin Kirkland: [https://insights.ubuntu.com/2016/02/18/zfs-licensing-and-linux/ ZFS Licensing and Linux], ubuntu.com, 18. februar 2016</ref> selv om en rekke Linuxdistribusjoner har hatt støtte for det.<ref name="ZFSonLinux">[http://zfsonlinux.org/ ZFS On Linux], Lawrence Livermore National Laboratory</ref>{{#tag:ref|Eksempler Linuxdistribusjoner som benytter eller har benyttet ZFS er Arch Linux, Debian, [[Fedora (Linux)|Fedora]], Gentoo, [[OpenSUSE]], Red Hat Enterprise Linux, [[CentOS]] og [[Ubuntu (operativsystem)|Ubuntu]] <ref name="ZFSonLinux"/>.|group="lower-alpha"|name="ZFS Linux"}} OpenZFS oppstod som en [[fork]] av ZFS i 2010,<ref>Bryan Cantrill: [http://www.slideshare.net/bcantrill/fork-yeah-the-rise-and-development-of-illumos Fork Yeah! The rise and Development of Illumos], slideshare.net, 8. desember 2011</ref> og støttes også av Linuxkjernen. Lisensieringsproblemene med ZFS har likevel helt klart bidratt til at btrfs vokste frem som et alternativ.<ref>[https://www.reddit.com/r/linux/comments/32cu9w/zfs_vs_btrfs/ ZFS Vs. BTRFS], reddit.com, 2015</ref>

XFS,<ref name="XFSdoc">[http://xfs.org/docs/xfsdocs-xml-dev/XFS_Filesystem_Structure/tmp/en-US/html/index.html XFS Filesystem Structure. Documentation of the XFS filesystem on-disk structures. Edition 0] {{Wayback|url=http://xfs.org/docs/xfsdocs-xml-dev/XFS_Filesystem_Structure/tmp/en-US/html/index.html |date=20161012230754 }}, xfs.org</ref> ReiserFS<ref name="reiserfsdok">Florian Buchholz: [http://jcoppens.com/univ/data/pdf/fs/reiserfs.pdf The structure of the Reiser file system], jcoppens.com, 17. september 2008</ref> og JFS<ref name="JFS_Archwiki">[https://wiki.archlinux.org/index.php/JFS JFS], Archwiki, 30. august 2016</ref> er implementert som [[B+ tre|B+ trær]]. Denne [[datastruktur]]en kan betraktes som en variant av [[B-tre|B-trær]], hvor hver node bare inneholder nøkler og ikke nøkkelpar. B+ trær er vanlig innenfor filsystemer.{{#tag:ref|Av andre filsystemer som bruker B+ trær kan vi nevne [[Novell Storage Services]] (NSS)<ref>[http://support.novell.com/techcenter/qna/dnq20021005.html We are redesigning an application that currently stores...], Micro Focus, 31. oktober 2002</ref>, [[NTFS]] (brukt til indeksering),<ref>[http://www.williballenthin.com/forensics/indx/ NTFS INDX Parsing] {{Wayback|url=http://www.williballenthin.com/forensics/indx/ |date=20161014061809 }}, williballenthin.com</ref> [[ReFS]],<ref>Michael Larabel: [http://www.phoronix.com/scan.php?page=news_item&px=MTA0NDA Microsoft's ReFS File-System: Competitor To Btrfs?], phoronix, 17. januar 2012</ref> [[Be File System]] (i [[BeOS]])<ref name="Giampaolo1998"/> og i [[HAMMER]],<ref>Timm Müller: [https://wr.informatik.uni-hamburg.de/_media/teaching/sommersemester_2012/sds-12-mueller-hammer-ausarbeitung.pdf HAMMER File System], wr.informatik.uni-hamburg.de, 13. juli 2012</ref> som er filsystemet til [[DragonFly BSD]].|group="lower-alpha"|name="filsystemer"}}

Reiser4 er implementert i form av et [[B* tre]].<ref>[https://reiser4.wiki.kernel.org/index.php/V4 V4], reiser4.wiki.kernel.org, 25. august 2016</ref> Et B* tre er en variant av et B-tre, som foretar en [[belastningsfordeling (informatikk)|belastningsfordeling]] mellom nabonoder internt i treet, for å pakke dem tettere.<ref name="Comer1979_129"/>

Som vi skal se, kan B+ trær ikke brukes på btrfs, fordi det er et [[copy-on-write]] filsystem.<ref name="USENIX"/> I stedet er btrfs implementert som et B-tre.<ref name="USENIX"/> Også ZFS og avleggeren OpenZFS er copy-on-write filsystemer, men de er implementert som [[hashtabell]]er. ZFS har mange likheter med btrfs på andre områder, og kunne ha blitt en konkurrent, hvis det ikke hadde vært for lisensieringsproblemene som er knyttet til det.

===B-trærs logaritmiske tidsaspekt===
{{utdypende|B-tre}}
[[Datastruktur]]en til btrfs er et B-tre, en selvbalanserende [[Tre (datastruktur)|tredatastruktur]], som sorterer data og tillater søking, sekvensiell aksess, innsettelse og sletting i en [[tidskompleksitet|logaritmisk tid]].<ref name="Btrfsdesign"/> Et søk gjennom en sortert tabell med <math>N</math> dataposter kan gjøres med omkring <math>\lceil \log_2 N \rceil</math> sammenligninger. Hvis tabellen har 1&nbsp;000&nbsp;000 dataposter, kan en spesifikk datapost bli lokalisert etter maksimum 20 sammenligninger: <math>\lceil \log_2 (1,000,000) \rceil = 20 </math>.

Informatikeren [[Douglas Earl Comer]] har angitt følgende beste og verste tilfeller av høyden på et B-tre:<ref name="Comer1979"/>
[[Fil:B-tree.svg|thumb|400px|right|Et [[B-tre]] av femte orden.]]
La ''h'' være høyden i et klassisk B-tre, ''n'' > 0 være antall innganger i treet, og ''m'' være maksimalt antall barn som en node kan ha. Hver node kan da ha maksimum ''m''−1 nøkler. Gjennom et [[induksjon]]sbevis kan vi da vise at høyden til treet, med alle sine noder fylt, har ''n''= ''m''<sup>''h+1''</sup>&minus;1 innganger. I det beste tilfellet er høyden av B-treet:

: <math>\lceil \log_{m} (n+1) \rceil -1</math>

La ''d'' være minimum antall barn som en intern node (ikke roten) kan ha. For et ordinært B-tre, er ''d''=⌈''m''/2⌉. Det verste tilfellet av høyden på et tre (hvor roten har høyde 0), blir derfor:

: <math>h \le \left\lfloor \log_{d}\left(\frac{n+1}{2}\right) \right\rfloor</math>

===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"/>

===Rot-treet===
Hvert tre opptrer som et objekt i rottreet (eller treet av trerøtter). Enkelte trær, slik som filsystemtrær og loggtrær, har et variabelt antall av instanser. Hver enkelt instans blir gitt sin egen objektid. Trær som er [[singleton]]er (datarelokasjons-trær, extent-trær og chunk-trær) tildeles en spesiell, fastsatt objektid ≤ 256. Rottreet opptrer for seg selv som et tre med objektid 1.

Trær refererer til hverandre gjennom objektid. De kan også referere til individuelle noder i andre trær som en triplett av treets objektid, som er nodens nivå innenfor treet og dens venstreplasserte   nøkkelverdi. Slike referanser er uavhengige av hvor treet blir lagret.

===Filsystemtreet===
Brukersynlige datafiler og [[Mappe (filsystem)|kataloger]] befinner seg i ''filsystemtreet''. Der er et filsystemtre per undervolum. Undervolumer kan nøstes, og i slike tilfeller opptrer de som et katalogelement (beskrevet nedenfor) hvis data er en referanse til det nøstede undervolumets filsystemtre.

Innenfor filsystemtreet har hver datafil og katalogobjekt et ''[[inode]]element''. [[Utvidede filattributter]] og tilgangen til [[aksesskontrolliste]]r blir lagret sammen med det separate elementet.

Innenfor hver katalog, opptrer et aksesspunkt til katalogen som et ''katalogelement'', hvor høyre nøkkelverdi er en [[syklisk redundanssjekk|CRC-32C]] [[hashfunksjon]] av deres filnavn. Dens data er en ''lokaliseringsnøkkel'', eller en nøkkel til inodeelementet den peker på. Katalogelementet kan således fungere som en indeks for oppslag i inodene, men er ikke brukt til iterasjon fordi de er sortert som en hashfunksjon som utfører en [[tilfeldig permutasjon]].
[[Fil:Fujitsu-Logo.svg|thumb|Logoen til [[Fujitsu]]. Det [[japan]]ske multinasjonale IT-konsernet Fujitsu Limited ([[japansk|nihongo]]: 富士通株式会社) er blant de som har bidratt til utviklingen av btrfs.]]
Dette betyr at brukerprogrammer som gjentatte ganger åpner filer i en stor katalog således vil generere mange flere disksøk mellom filer som ikke er naboer i treet. Dette medfører en nevneverdig svekkelse i ytelsen til andre filsystemer med hashfunksjonordnede kataloger. Dette gjelder blant annet ReiserFS,<ref>{{cite web|url = http://lkml.indiana.edu/hypermail/linux/kernel/0112.0/2019.html|title = Re: Ext2 directory index: ALS paper and benchmarks|work = ReiserFS developers mailing list|first = Hans|last = Reiser|date = 2001-12-07|accessdate = 2009-08-28}}</ref> ext3 (med Htre-indekser aktivert<ref>{{cite web|url = http://oss.oracle.com/~mason/acp/|first = Chris|last = Mason|title = Acp|work = Oracle personal web page|accessdate = 2011-11-05|archive-date = 2021-05-16|archive-url = https://web.archive.org/web/20210516204043/https://oss.oracle.com/~mason/acp/|url-status = yes}}</ref>) og ext4, som alle har navn som er krytptiserte ved hjelp av [[Tiny Encryption Algorithm]]. For å unngå dette, må hver katalog aksesseres av et katalogindekselement, der de høyre bitene av elementets nøkkelverdi er satt til en katalogteller som inkrementeres for hver ny katalogtilgang. Gjentagelser av disse indekselementene returnerer således katalogaksesser i omtrent samme rekkefølge som de er lagret på disken.

I tillegg til inode-elementer, har filer og kataloger også et referanseelement hvor nøkkelverdien i de høyre bitene er satt til objektid til deres foreldrekatalog. Datadelen av referanseelementet er filnavnet som inoden er kjent under i denne katalogen. Dette gjør det mulig å traversere oppover gjennom kataloghierarkiet og sørger for en måte til å veilede inodene tilbake til veiene i treet.

Filer med [[fast kobling|faste koblinger]] i flere kataloger har flere referanseelementer, et for hver foreldrekatalog. Filer med ''flere'' faste koblinger i samme katalog pakker alle koblingens filnavn inn i det samme referanse-element. Der var en konstruksjonsfeil som begrenset antallet faste koblinger i samme katalog til det som var mulig å pakke inn i en enkelt treblokk (som standard er blokkstørrelsen 4 Kb, filnavn har en gjennomsnittlig lengde på 8 bytes og hodet til filnavn er gjennomsnittlig 4 bytes. Dette gir mindre enn 350.). Applikasjoner som gjorde mye bruk av flere faste koblinger til samme katalog, slik som [[Git]], [[Gnus]], [[GMame]] og [[BackupPC]], viste seg senere å krasje etter at de hadde nådd denne grensen.<ref name="hard_link_limit">{{cite web|title=Hard Link Limitation |date=8. august 2010 |accessdate=2011-11-14 |work=kerneltrap.org |url=http://kerneltrap.org/mailarchive/linux-btrfs/2010/8/2/6885208/thread |url-status=dead |archiveurl=https://web.archive.org/web/20120401234546/http://kerneltrap.org/mailarchive/linux-btrfs/2010/8/2/6885208/thread |archivedate=2012-04-01 }}</ref> Denne grensen ble til slutt fjernet<ref>{{citation |title=btrfs: extended inode refs |first=Mark |last=Fasheh |date=2012-10-09 |accessdate=2012-11-07 |url=https://git.kernel.org/?p=linux/kernel/git/mason/linux-btrfs.git;a=commit;h=f186373fef005cee948a4a39e6a14c2e5f517298 |archiveurl=https://archive.today/20130415062145/http://git.kernel.org/?p=linux/kernel/git/mason/linux-btrfs.git;a=commit;h=f186373fef005cee948a4a39e6a14c2e5f517298# |url-status=dead }}</ref> (en forandring som ble integrert i versjon 3.7 av Linuxkjernen<ref>{{citation |title=Pull btrfs update from Chris Mason |first=Linus |last=Torvalds |date=2012-10-10 |accessdate=2012-11-07 |url=https://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commitdiff;h=72055425e53540d9d0e59a57ac8c9b8ce77b62d5 |work=git.kernel.org |archiveurl=https://archive.today/20130415043758/http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commitdiff;h=72055425e53540d9d0e59a57ac8c9b8ce77b62d5# |url-status=dead }}</ref>) ved å introdusere ''utvidede referanseelementer'' som kunne holde rede på faste koblinger.

====«Extents»====
[[Fil:Red Hat Tower-2013-10-29.jpeg|thumb|Raleigh's Red Hat Tower. Det amerikanske programvareselskapet [[Red Hat]] har hatt en sentral rolle i utviklingen av btrfs.{{byline|Foto:Mark Turner|29. oktober 2013}}]]
Fildata holdes utenfor treet i ''[[extent]]s'', som stadig kjører på diskblokker. Størrelsen på en extent-blokk er 4 Kb i størrelse som standard, har ikke hoder og inneholder bare fildata (som kan være komprimert). I komprimerte extents, er individuelle blokker ikke komprimert separat; i stedet omfatter kompresjonen av strømmen den enkelte extent i sin helhet.

Filer har ''utvidede dataelementer'' som holder rede på de extents som holder på deres innhold. Den høyre delen av elementets nøkkelverdi er det innledende byte offset til denne extent. Dette gjør det mulig å foreta effektive søk i store filer med mange extents, fordi den korrekte extent for enhver gitt filoffset kan beregnes med bare et enkelt oppslag i treet.

Snapshots og klonede filer deler extents. Når en liten del av en større slik extent blir overskrevet, kan det resulterende copy-on-write skape tre nye extents: En liten en som inneholder de overskrevne data, og to større som har umodifiserte data på hver side av overskrivingen. For å unngå å måtte skrive umodifiserte data på nytt, kan copy-on-write i stedet skape ''bookend'' extents, eller extents som kort og godt er deler av eksisterende extents. Extent dataelementer tillater således å inkludere en offset til den extent som de sporer; elementer for ''bookends'' er de som har offset som ikke er lik null.<ref name="btrfs-wiki-1" />

Hvis datafilen er liten nok til å passe innenfor en trenode, blir den i stedet dyttet inn i treet og lagret på innsiden av dataelementets extent. Hver trenode er lagret i sin egen treblokk &ndash; en enkelt ukomprimert blokk med et hode. Treblokken blir betraktet som en frittstående enkeltblokk-extent.

===Extent allokasjonstre===
Extent allokasjonstreet fungerer som et allokasjonskart for filsystemet. I motsetning til andre trær, har ikke elementene i dette treet objektid'er og representerer regioner av plass: Deres nøkkelverdier til venstre og til høyre er den innledende offset og lengden til regionene som de representerer.
[[Fil:Suse-logo.PNG|thumb|Logoer til SuSe. Det tyske programvareselskapet [[SuSE]] (''Software und Systementwicklung'') er en av bidragsyterne til btrfs]]
Filsystemets inndeler dets allokerte plass i ''blokkgrupper'', som er allokerte regioner av variabel størrelse som alternerer suksessivt mellom de valgte metadata extents (trenoder) og data extents (filinnhold). Standard ratio mellom data og metadata blokkgrupper er 1:2. De er ment å arbeide som [[Orlov blokkallokator]]en og blokkgruppene i ext3 ved å allokere relaterte filer sammen og unngå fragmentering ved å etterlate seg allokasjonsgap mellom gruppene. ext3 blokkgrupper har fastsatte lokasjoner som er beregnet ut fra størrelsen på filsystemet, mens de i btrfs er dynamiske og skapes etter behov. Hver blokkgruppe er assosiert med et ''blokkgruppe-element''. Inodeelementer i filsystemtreet inkluderer en referanse til deres nåværende blokkgruppe.<ref name="btrfs-wiki-1" />

Extent elementer inneholder en referanse bakover til den trenoden eller den filen som inneholder denne extent. Det kan være flere slike referanser bakover hvis en extent er delt mellom flere snapshots. Hvis der er for mange referanser bakover til at de kan fylle elementet, omdannes de til individuelle ''extent datareferanse-elementer''. Trenoder har i sin tur referanser tilbake til trærne som inneholder dem. Dette gjør det mulig å finne hvilke extents eller trenoder som befinner seg i en region ved å foreta et B-tre ''range lookup'' på offsetpar som er knyttet til denne regionen og deretter følge referansene bakover. For relokalisering av data, tillater dette en effektiv traversering oppover fra de relokaliserte blokkene for raskt å finne og ordne alle referanser til disse blokkene, uten å måtte gå gjennom hele filsystemet. Dette gjør det også mulig for filsystemet å effektivt minske, flytte og defragmentere dets lagring online.

Extent allokasjonstreet er, som alle andre trær i filsystemet, copy-on-write. Når man skriver til filsystemet kan man således forårsake en kaskade hvor endrede trenoder og fildata resulterer i at nye extents blir allokert, slik at extenttreet selv blir forandret. For å unngå å skape en [[tilbakekobling]], kan extent trenoder som fortsatt er i minnet men ennå ikke er lagret på disken bli oppdatert på stedet for å reflektere de nye copy-on-write extents.

I teorien gjør extent allokasjonstreet en konvensjonell [[free-space bitmap]] unødvendig fordi extent allokasjonstær fungerer som en B-tre versjon av et [[BSP-tre]]. I praksis blir likevel et [[rød-svart tre]] med bitmaps av [[Side (dataminne)|sidestørrelse]] brukt for å øke hastigheten på allokasjonene. Siden versjon 2.6.37 av Linuxkjernen, via mount-opsjonen ''space_cache'',<ref>{{cite web| title = Benchmarks Of The Btrfs Space Cache Option|accessdate = 2012-11-16|date = 2010-12-24|first = Michael|last = Larabel|url = https://www.phoronix.com/scan.php?page=article&item=btrfs_space_cache&num=1|publisher = [[Phoronix]]}}</ref> er disse bitmaps vedvarende tilstede på disken som spesielle extents som er unntatt fra sjekksummer og copy-on-write. Extentelementet som sporer disse extents blir lagret i rottreet.

===Sjekksumtreet og data scrubbing===
{{utdypende|Datakorrupsjon}}
[[Fil:Intel Core I7-920 Boxed - 14.JPG|thumb|En Intel Core i7 920 [[mikroprosessor]]. [[Intel|Intel Corporation]] er mest kjent for å produsere mikroprosessorer, men har også en avdeling for programvareutvikling og har vært en av bidragsyterne til btrfs.]]
[[CRC-32C]] sjekksummer blir beregnet for både data og metadata og blir lagret som ''sjekksumelementer'' i ''sjekksumtreet''. Det er plass til 256 biter for metadata sjekksummer og opp til en full løvblokk (omkring 4 Kb eller mer) for datasjekksummer. Opsjoner for flere sjekksumalgoritmer er planlagt i fremtiden.<ref name="features"/><ref name="checksumFAQ">{{cite web
 | url = https://btrfs.wiki.kernel.org/index.php/FAQ#What_checksum_function_does_Btrfs_use.3F
 | title = FAQ - btrfs Wiki: What checksum function does Btrfs use? 
 | accessdate = 2013-09-19
 | publisher = The btrfs Project
}}</ref>

Det er et sjekksumelement per kontinuerlig kjøring av allokerte blokker, med sjekksummer per blokk pakket inn i elementdataene. Hvis det er flere sjekksummer enn det er plass for, flyttes de over til et nytt sjekksumelement i et nytt løv. Hvis filsystemet oppdager en sjekksum-mismatch mens det leser en blokk, prøver det først å hente eller skape en god kopi av denne blokken fra et annet utstyr, hvis intern speiling eller [[RAID]]-teknikker er i bruk.<ref name="oracle-advanced-btrfs">{{cite web
 | url = http://www.oracle.com/technetwork/articles/servers-storage-admin/advanced-btrfs-1734952.html
 | title = How I Use the Advanced Capabilities of Btrfs
 | date = August 2012 | accessdate = 2013-09-20
 | first1 = Margaret | last1 = Bierman
 | first2 = Lenz | last2 = Grimmer
}}</ref><ref>{{cite web |last=Salter |first=Jim |title=Bitrot and atomic COWs: Inside "next-gen" filesystems |url=http://arstechnica.com/information-technology/2014/01/bitrot-and-atomic-cows-inside-next-gen-filesystems/ |publisher=Ars Technica |accessdate=15. januar 2014 |date=15. januar 2014 |url-status=dead |archiveurl=https://www.webcitation.org/6XEwjmpKg?url=http://arstechnica.com/information-technology/2014/01/bitrot-and-atomic-cows-inside-next-gen-filesystems/ |archivedate=2015-03-23 }}</ref>

Btrfs kan foreta en online sjekk av hele filsystemet ved å trigge en [[data scrubbing]] i bakgrunnen. Denne skanner hele filsystemet, sjekker dets integritet og prøver automatisk å rapportere og reparere enhver skadet blokk, hvis noe slikt finnes underveis.<ref name="oracle-advanced-btrfs" /><ref>{{cite web
 | url = https://blogs.oracle.com/wim/entry/btrfs_scrub_go_fix_corruptions
 | title = btrfs scrub - go fix corruptions with mirror copies please!
 | date = 2011-09-28 | accessdate = 2013-09-20
 | first = Wim | last = Coekaerts
}}</ref>

===Loggtreet===
En [[sync (Unix)|fsync]] er en forespørsel om å sende modifiserte data øyeblikkelig til et stabilt [[lagringsmedium]]. Programmer som ofte benytter fsync (slik som databaser) kan potensielt generere en stor mengde redundante skrivinger ved å tvinge filsystemet til å repetere copy-on-write og således ofte sende forespørsler om modifiserte deler av treet til lagring. For å unngå dette blir det skapt et midlertidig loggtre per undervolum for å journalføre copy-on-write som er trigget av fsync. Loggtrær sporer sitt eget innhold og holder sine egne sjekksumelementer. Deres elementer blir gjennomgått på nytt og slettet under neste skriving av hele treet (hvis der var et systemkrasj) under neste mouting.

===Chunk- og utstyrstrær===
[[Utstyrsblokker]] er inndelt i ''chunks'' på 256 Mb eller mer. Chunks kan bli speilet eller [[datastriping|stripet]] over flere former for utstyr. Speilingen eller stripingen er transparent for resten av filsystemet, som bare ser et enkelt, logisk adresserom som chunks blir plassert innenfor.
[[Fil:IFA 2012 IMG 5889.JPG|thumb|Det globale amerikanske nettverkselskapet NETGEAR, Inc. er blant bidragsyterne til btrfs]]
Alt dette blir sporet av ''chunktreet'', hvor hvert utstyr er representert som et utstyrselement og enhver mapping fra en logisk chunk til den underliggende fysiske chunk blir lagret i et chunk ''kartleggingselement''. Utstyrstreet er det inverse av chunk-treet, og inneholder extentelementer for utstyr som mapper byterekkefølgen til utstyrsblokkene tilbake til de enkelte chunks. Liksom tilfellet er i extent allokasjonstrær, tillater dette btrfs å effektivt begrense eller fjerne utstyr fra volumer ved å lokalisere de chunks som de inneholder (og relokalisere deres innhold).

Filsystemet, chunks og utstyr blir alle tildelt en [[Universally Unique Identifier]] (UUID). Hodet til enhver trenode inneholder både UUID til dens tilhørende chunk og UUID til filsystemet. De ulike chunks i chunktreet, rottreet, utstyrstreet og extenttreet blir alltid speilet, selv på volumer med et enkelt utstyr. Disse har alle som intensjon å forbedre oddsene for en vellykket berging av data i tilfeller av [[skadd sektor|skadde sektorer]].

===Relokasjonstrær===
Defragmentering, minsking av volumstørrelsen og rebalanseting krever at extents blir relokalisert. Likevel, ved å foreta en enkel copy-on-write på den relokaliserte extent, vil man bryte delingen mellom snapshots og brukerens diskområde. For å bevare delingen, benyttes en oppdater-og-swap [[algoritme]], hvor et spesielt ''relokasjonstre'' fungerer som et diskområde for de rammede metadata. Den extent som skal relokaliseres blir først kopiert til dens destinasjon. Ved å følge de tilbakeførende referansene oppover gjennom undervolumets filsystemtre, blir metadata som peker på de gamle extent progressivt oppdatert til å peke på de nye; ethvert nylig oppdatert element blir lagret i relokasjonstreet. Når oppdateringen er fullført, blir elementene i relokasjonstreet swappet med deres motparter i det undervolum som er påvirket, og relokasjonstreet blir forkastet.<ref>{{citation|title = BTRFS: The Linux B-tree Filesystem|date = 2012-07-09|first1 = Chris|last1 = Mason|first2 = Ohad|last2 = Rodeh|first3 = Josef|last3 = Bacik|publisher = IBM Research|url = http://domino.watson.ibm.com/library/CyberDig.nsf/papers/6E1C5B6A1B6EDD9885257A38006B6130/$File/rj10501.pdf|accessdate = 2012-11-12|archivedate = 2020-02-03|archiveurl = https://web.archive.org/web/20200203064847/https://domino.watson.ibm.com/library/CyberDig.nsf/papers/6E1C5B6A1B6EDD9885257A38006B6130/$File/rj10501.pdf}}</ref>

===Superblokker===
[[Fil:Strato 201x logo.svg|thumb|[[Strato AG]], et datterselskap av [[Deutsche Telekom]], er blant dem som har deltatt i utviklingen av btrfs]]
Alle filsystemets trær, inkludert chunktreet selv, er lagret i chunks, noe som skaper et potensielt [[høna og egget]]-problem når man mounter filsystemet. Når man foretar en [[oppstart]] av en mounting, må en liste med fysiske adresser til chunks som tilhører disse chunks og rottrærne bli lagret i [[utstyrsfil|superblokken]].<ref>{{cite web | url = http://btrfs.wiki.kernel.org/index.php/Multiple_Device_Support |url-status=dead | first= Chris |last=Mason | work = Btrfs wiki | accessdate = 5. november 2011 | date = 30. april 2008 |title = Multiple device support | archivedate= 20. juli 2011 |archiveurl= https://web.archive.org/web/20110720220543/https://btrfs.wiki.kernel.org/index.php/Multiple_Device_Support }}</ref>

Speilinger av superblokker blir lagret på faste lokasjoner:<ref>Sean Bartell: [http://kerneltrap.org/mailarchive/linux-btrfs/2010/4/20/6884623 Re: Restoring BTRFS partition], linux-btrfs, 20. april 2010</ref> 64 Kb i hver utstyrsblokk, med tilleggskopier ved 64 Mb, 256 Gb og 1 Pb. Når et superblokk-speil blir oppdatert, inkrementeres dets generasjonsnummer. Under mounting brukes kopien med det høyeste generasjonstallet. Alle speil av superblokker blir oppdatert ved siden av hverandre, bortsett fra i [[Solid state drive]]-modus som alternerer oppdateringer blant speilene for å sørge for [[wear levelling]].