Editing B-tree (section)

==In filesystems==
In addition to its use in databases, the B-tree (or {{section link||Variants}}) is also used in filesystems to allow quick random access to an arbitrary block in a particular file. The basic problem is turning the file block <math>i</math> address into a disk block address.

Some operating systems require the user to allocate the maximum size of the file when the file is created. The file can then be allocated as contiguous disk blocks. In that case, to convert the file block address <math>i</math> into a disk block address, the operating system simply adds the file block address <math>i</math> to the address of the first disk block constituting the file. The scheme is simple, but the file cannot exceed its created size.

Other operating systems allow a file to grow. The resulting disk blocks may not be contiguous, so mapping logical blocks to physical blocks is more involved.

[[MS-DOS]], for example, used a simple [[File Allocation Table]] (FAT). The FAT has an entry for each disk block,<ref group="note">For FAT, what is called a "disk block" here is what the FAT documentation calls a "cluster", which is a fixed-size group of one or more contiguous whole physical disk [[Cylinder-head-sector|sectors]]. For the purposes of this discussion, a cluster has no significant difference from a physical sector.</ref> and that entry identifies whether its block is used by a file and if so, which block (if any) is the next disk block of the same file. So, the allocation of each file is represented as a [[linked list]] in the table. In order to find the disk address of file block <math>i</math>, the operating system (or disk utility) must sequentially follow the file's linked list in the FAT. Worse, to find a free disk block, it must sequentially scan the FAT. For MS-DOS, that was not a huge penalty because the disks and files were small and the FAT had few entries and relatively short file chains. In the [[FAT12]] filesystem (used on floppy disks and early hard disks), there were no more than 4,080 <ref group="note">Two of these were reserved for special purposes, so only 4078 could actually represent disk blocks (clusters).</ref> entries, and the FAT would usually be resident in memory. As disks got bigger, the FAT architecture began to confront penalties. On a large disk using FAT, it may be necessary to perform disk reads to learn the disk location of a file block to be read or written.

[[TOPS-20]] (and possibly [[TENEX (operating system)|TENEX]]) used a 0 to 2 level tree that has similarities to a B-tree.{{Citation needed|date=October 2009}} A disk block was 512 36-bit words. If the file fit in a 512 (2<sup>9</sup>) word block, then the file directory would point to that physical disk block. If the file fit in 2<sup>18</sup> words, then the directory would point to an aux index; the 512 words of that index would either be NULL (the block isn't allocated) or point to the physical address of the block. If the file fit in 2<sup>27</sup> words, then the directory would point to a block holding an aux-aux index; each entry would either be NULL or point to an aux index. Consequently, the physical disk block for a 2<sup>27</sup> word file could be located in two disk reads and read on the third.

Apple's filesystem [[HFS+]] and [[APFS]], Microsoft's [[NTFS]],<ref name=insidewin2kntfs>{{cite web|url=http://msdn2.microsoft.com/en-us/library/ms995846.aspx|title=Inside Win2K NTFS, Part 1|author=Mark Russinovich|date=30 June 2006|author-link=Mark Russinovich|publisher=[[MSDN|Microsoft Developer Network]]|access-date=2008-04-18|archive-url=https://web.archive.org/web/20080413181940/http://msdn2.microsoft.com/en-us/library/ms995846.aspx|archive-date=13 April 2008<!--DASHBot-->|url-status=live}}</ref> AIX (jfs2) and some [[Linux]] filesystems, such as [[Bcachefs]], [[Btrfs]] and [[ext4]], use B-trees.

B<sup>*</sup>-trees are used in the [[Hierarchical File System (Apple)|HFS]] and [[Reiser4]] [[file system]]s.

[[DragonFly BSD]]'s [[HAMMER (file system)|HAMMER]] file system uses a modified B+-tree.<ref>{{cite web|url=https://www.dragonflybsd.org/hammer/hammer.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.dragonflybsd.org/hammer/hammer.pdf |archive-date=2022-10-09 |url-status=live|date=2008-06-21|author=Matthew Dillon|title=The HAMMER Filesystem}}</ref>