> Подсказка: то, что было с btrfs, можно прекрасно получить и на O(n).

В жопу надо ваш БТРфс засунуть

# mkfs.btrfs -l32k -n32k -m single /dev/sdd1
# mount -t btrfs -o noatime,discard,ssd /dev/sdd1 /media/flash/
# cd /media/flash 
# /opt/iozone/bin/iozone -a -b /btrfs.xls -+u -p -B -e -E;
        Iozone: Performance Test of File I/O
                Version $Revision: 3.283 $
                Compiled for 64 bit mode.
                Build: linux-AMD64 
       Contributors:William Norcott, Don Capps, Isom Crawford, Kirby Collins
                     Al Slater, Scott Rhine, Mike Wisner, Ken Goss
                     Steve Landherr, Brad Smith, Mark Kelly, Dr. Alain CYR,
                     Randy Dunlap, Mark Montague, Dan Million, 
                     Jean-Marc Zucconi, Jeff Blomberg, Benny Halevy,
                     Erik Habbinga, Kris Strecker, Walter Wong.
        Run began: Tue Dec 25 19:32:40 2012
        Auto Mode
        CPU utilization Resolution = 0.001 seconds.
        CPU utilization Excel chart enabled
        Purge Mode On
        Using mmap files
        Include fsync in write timing
        Command line used: /opt/iozone/bin/iozone -a -b /btrfs.xls -+u -p -B -e -E
        Output is in Kbytes/sec
        Time Resolution = 0.000001 seconds.
        Processor cache size set to 1024 Kbytes.
        Processor cache line size set to 32 bytes.
        File stride size set to 17 * record size.
                                                            random  random    bkwd  record  stride                                   
              KB  reclen   write rewrite    read    reread    read   write    read rewrite    read
              64       4    2154    2285   615952   710511  727850    2331  679917    2752 1363961
              64       8    2162    2316   695778   703068  939223    2502  551422    2711 1183548
              64      16     151    2284   673098  1304314 1363961    2248  889431    2668 1780008
              64      32    2338    2196   710511   998622 1526887    2227 1087638    2276 1143223
              64      64    2277    2285   647135   969761 1163036    2319  955947    2353  727850
             128       4    3568    3357   590094   695603  811221    4487  509943    5505  666253
             128       8    3424    3507   681476   612303  837806    4570  707520    5419 1561553
             128      16    3254    3617   568836   598647  633247    4388  582412    5505 1022989
             128      32    3556    3483   533241   493989  604036    3863  422464    4533  735635
             128      64    3580    3570   404025   529038  615814    4412  387966    4457  955616
             128     128    3503     298   347758   509943  500436     582  456986    3471  486822
             256       4    5265    5334   635047   699139  810490    6998  600928    9917  773697
             256       8    5673    5319   609801   738065  900936    6818  686620     617  577962
             256      16    5237    5292   548161   603630  653204    6177  542347   10723 1117543
             256      32    5347    5333   518263   572721  664935    7080  547044    9998  785584
             256      64    5835    5705   474098   541253  547044    6114  511109    8828  713067
             256     128    6482    7136   465466   514045  596587    7937  489442    7733  615393
             256     256    6687    7039   439732   485678  506767    6783  428159    5989  425951
             512       4    6826    7135   532767   681566  819085    9279  519367   21228  591951
             512       8    7198    7086   568296   696600  836636    9500  600223   20802  588383
             512      16    1112     909   519241   571472  678122   12604  450318   20504  464541
             512      32    1135   10058   473660   540681  608041   12354  484452   19240  843206
             512      64    9525   10014   455960   516618  621233   14551  493242   17506  733478
             512     128   10241   10240   565156  1089647 1333173   12867  803757   14953 1510391
             512     256   10584   10401   395353   486207  572081   13660  399397   13174  521385
             512     512    9982   10222   565156   568899  559560    9387  331156   10068  333314
            1024       4    1762    2019   559619   563288  732453   12615  537488   51207  535011
Ошибка сегментирования

Это ещё не всё...

------------[ cut here ]------------
kernel BUG at fs/btrfs/extent-tree.c:1481!
invalid opcode: 0000 [#2] PREEMPT SMP 
CPU 3 
Modules linked in: btrfs zlib_deflate zlib_inflate ipt_ECN ipt_REJECT iptable_filter xt_recent iptable_mangle xt_DSCP 8250_pnp sr_mod nvidia(O) et131x(C) cdrom 8250 serial_core ohci_hcd evdev
Pid: 3327, comm: btrfs-transacti Tainted: G      D WC O 3.7.1 #1 TYAN Computer Corp. S2895/S2895
RIP: 0010:[<ffffffffa08c175e>]  [<ffffffffa08c175e>] 0xffffffffa08c175e
RSP: 0018:ffff8801524b5ac0  EFLAGS: 00010202
RAX: 0000000000000001 RBX: ffff880241178540 RCX: 0000000000000000
RDX: 0000000000000008 RSI: 0000160000000000 RDI: 0000000000000000
RBP: 0000000000000000 R08: 0000000000000000 R09: 0000000000000000
R10: 0000000000000000 R11: 0000000000000000 R12: 00000000000000b2
R13: 00000000ffffffff R14: ffff8802411515b0 R15: ffff8802411515b0
FS:  00007f98822b4740(0000) GS:ffff88025fd00000(0000) knlGS:0000000000000000
CS:  0010 DS: 0000 ES: 0000 CR0: 000000008005003b
CR2: 00007fb195144000 CR3: 00000000015d6000 CR4: 00000000000006e0
DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
DR3: 0000000000000000 DR6: 00000000ffff0ff0 DR7: 0000000000000400
Process btrfs-transacti (pid: 3327, threadinfo ffff8801524b4000, task ffff880152690040)
Stack:
 ffff88025269a800 000000000000003d ffff88025368f800 00000000000004b1
 0000000000e6a000 ffff8801524b5bf0 0000000000000000 ffffffffffffffff
 0000000000000000 a000000000000000 00a80000000000e6 ff00000000000020
Call Trace:
 [<ffffffffa08c1841>] ? 0xffffffffa08c1841
 [<ffffffff81100eae>] ? 0xffffffff81100eae
 [<ffffffffa08c2a09>] ? 0xffffffffa08c2a09
 [<ffffffffa08c50a9>] ? 0xffffffffa08c50a9
 [<ffffffffa08db44e>] ? 0xffffffffa08db44e
 [<ffffffff810671c0>] ? 0xffffffff810671c0
 [<ffffffffa08dc37e>] ? 0xffffffffa08dc37e
 [<ffffffff810519c0>] ? 0xffffffff810519c0
 [<ffffffffa08d30b5>] ? 0xffffffffa08d30b5
 [<ffffffffa08d2e50>] ? 0xffffffffa08d2e50
 [<ffffffffa08d2e50>] ? 0xffffffffa08d2e50
 [<ffffffff81066a00>] ? 0xffffffff81066a00
 [<ffffffff814e8374>] ? 0xffffffff814e8374
 [<ffffffff81066980>] ? 0xffffffff81066980
 [<ffffffff814e8370>] ? 0xffffffff814e8370
Code: 65 e8 67 f9 03 00 e9 bc fd ff ff b8 fe ff ff ff e9 a8 fb ff ff be ef 05 00 00 48 c7 c7 4f 52 93 a0 e8 97 16 78 e0 e9 c1 fb ff ff <0f> 0b 0f 0b 0f 0b 66 66 66 2e 0f 1f 84 00 00 00 00 00 41 57 49 
RIP  [<ffffffffa08c175e>] 0xffffffffa08c175e
 RSP <ffff8801524b5ac0>
---[ end trace 0000000000001209 ]---