Redigerer Btrfs (avsnitt)

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