Increase the size of the 'message' buffer, which is currently

[sgt/tweak] / btree.but

\cfg{html-leaf-level}{0}
\cfg{chapter}{Section}
\cfg{text-title-align}{left}
\cfg{text-indent}{0}
\cfg{text-chapter-numeric}{yes}
\cfg{text-chapter-suffix}{. }
\cfg{text-chapter-underline}{-}
\cfg{text-section-numeric}{0}{yes}
\cfg{text-section-suffix}{0}{. }
\cfg{text-section-underline}{0}{-}
\cfg{html-chapter-numeric}{yes}
\cfg{html-chapter-suffix}{. }
\cfg{html-section-numeric}{0}{yes}
\cfg{html-section-suffix}{0}{. }
\cfg{html-section-numeric}{1}{yes}
\cfg{html-section-suffix}{1}{. }

\title An Efficient Data Structure For A Hex Editor

by \W{http://pobox.com/~anakin/}{Simon Tatham}

\C{intro} Introduction

Hex editors have been around for a long time, and at the very basic
level they are very simple to write. Since they are mostly used for
editing files such as executables, which contain a lot of
cross-references to particular byte positions in the file, a hex
editor need not have an insert mode in order to be useful. And a hex
editor without an insert mode is very easy to implement: you simply
allocate a large enough array for the input file, and use that as
your data structure. The only operation you really need to be able
to do efficiently is to jump to a particular byte position, and
that's precisely what an array makes easy.

On the other hand, an insert mode can be useful in other
circumstances. Not \e{all} types of file you might want to edit have
the same restrictions as an executable. And as soon as you want your
hex editor to have an insert mode, the data structure question
becomes much more interesting.

In this article I present an efficient and scalable data structure
which supports all the operations needed by a hex editor.

\C{simple} Simple options

One technique used to support insert mode in editors is to use an
array larger than the file size, with a gap in it. The file contents
up to the current cursor position are stored at the start of the
array; the file contents from the current cursor position to the end
are stored at the end of the array; and the gap in the middle moves
about as the cursor does.

This makes insertion easy. When the user inserts an extra character,
you just add it to one end or other of the gap. On the other hand,
\e{moving} through the file now becomes a slow operation; it's not
noticeable when you're moving by a byte, by a line, or even by a
screenful at a time, but as soon as you try to jump to the start or
end of the file, or jump to a particular specified file offset,
suddenly the editor has to bodily shift enormous amounts of file
data from one end of the gap to the other.

Another slightly better option is to use a linked list of small
arrays, and to let the arrays vary in size between K and 2K bytes,
for some fixed minimum block size K. Inserting a single byte in the
middle of a block doesn't cost too much; occasionally the block will
grow beyond size 2K and have to be split into two smaller ones, but
even that isn't too slow.

Jumping to a particular position, however, is still an O(N)
operation using this structure. In practice it isn't \e{too} bad,
since the length of the linked list is at worst 1/K times the size
of the file; but once the file size becomes seriously big, this
approach does not scale well.

The common problem in both these methods is that as soon as you make
insertion a constant-time operation, seeking to a given byte
position becomes linear-time. Whereas in the original array format,
of course, seeking was constant-time but \e{insertion} became
linear-time.

\C{trees} Using balanced trees

This is where trees come in. Balanced tree structures (any of AVL
trees, red-black trees and B-trees) all solve this sort of problem
for sorted lists. You can insert an element into a balanced tree in
\e{log} time, and you can search for a particular element in log
time as well. This sounds like the kind of compromise we want: if
making insertion constant-time forces seeking to be linear and vice
versa, we would prefer to arrange for \e{both} to be log-time.

The conventional use of a balanced tree to store a sorted list,
however, is not immediately helpful to us. The only criterion we
could reasonably sort on would be byte position in the file; and as
soon as we store our data as a set of (position, data) pairs, we're
back to insertion being linear again, because we would have to alter
the position field of every tree element after the insertion point.

Is there anything we can do to our balanced trees to make this work
better?

\C{counted-trees} Counted trees

Yes, there is.

Suppose you add an additional field to every node of a balanced
tree. In that field, you store a count of the number of elements \e{in
or below} that node.

Operations which alter the tree (insertion and deletion) now have to
make sure these counts remain accurate. This can be done without
sacrificing the log-time characteristics of the operations. For
example, when you add an element, you increment the count of the
node containing it, and then work back up the tree to the root
incrementing the counts in all the nodes you go past. Since the
height of the tree is O(log N), this only takes you O(log N) time.

So we can add counts to a tree and still maintain it efficiently.
What have the counts bought us?

Once we have counts in a tree, they introduce an entirely new way to
\e{search} the tree. Starting at the root, we can search down the
tree by examining the count fields rather than comparing elements as
usual; and this allows us to find the Nth item in the tree, for any
N, in a single log-time search. For example, suppose the root tree node
contains a child with count 54, then an actual element, then a child
with count 73. Then:

\b If you are trying to get to a position less than 54, then you
descend straight to the leftmost child.

\b If you are trying to get to \e{exactly} position 54, you return
the element out of the root node.

\b If you are trying to get to position 55 or greater, you descend
to the rightmost child, and subtract 55 from your desired position.
(If you want element 57 of the tree, then you know there are 55
elements in the tree before the right-hand subtree, so you know you
want element 2 of the right-hand subtree.)

So now we have a means of finding the Nth item in a tree in a
log-time search. This is starting to look promising.

The trouble is, we're still stuck with having some sort of sorting
order on the tree. Now we need to deal with that.

\C{unsorted-trees} Unsorted trees

The simple answer to the sorting problem is to do away with sorting
the tree at all!

Conventional balanced trees have a sorting order because it's used
to find elements in the tree, and to know where to add an element.
But we don't need a sorting order to find things any more, because
we can use a count-based search to jump to the Nth position. Can we
also use counts during the tree add operation, to allow us to
specify \e{where} we want to add our new element?

We can. Tree add algorithms start by searching down the tree to find
the position where the new element will be inserted. If we do this
search using counts, in exactly the same way described in
\k{counted-trees}, then we can add any element we like at any
position in the tree. Once we do this, of course, we have to throw
out the sorting order completely, and never do another order-based
search or insertion again, because they won't work. But that's OK,
because we didn't need them anyway.

Now we have exactly what we were after in the first place. We
have a data structure which stores an unordered list of items, in
such a way that we can insert or delete an item in log time \e{and}
find the Nth element in log time.

\C{splitjoin} Splitting and joining trees

Now we can begin to get more ambitious. One issue we have not
addressed yet is cut and paste.

So far I have discussed tree insertion in the assumption that you
only ever insert one character at a time into your tree. In fact hex
editors need cut and paste just as much as normal text editors do;
so we must think about how to insert or remove a larger block of
data at a time.

One obvious way is to process each byte individually. A ten-byte
cut operation is ten individual deletions, and a ten-byte paste is
ten individual insertions. This is fine if you only ever use cut and
paste to move tiny chunks of data around a large file, but if you
need to move \e{half the file} from one place to another, things get
more interesting.

The linked-list structure discussed in \k{simple} would have helped
a lot with this problem. Linked lists don't just make it easy to
insert or delete one item: they make it just as easy to unlink an
enormous chunk of a list once you've found both ends of the chunk,
and you can link that chunk in somewhere else easily as well.

It turns out that you \e{can} do the same thing with balanced trees.
At this point it starts to make a difference what kind of balanced
tree you use: all three of AVL, red-black and B-trees support these
operations, but the precise methods vary between them. I'm going to
use B-trees from here on, because the algorithms are slightly simpler.

What we need are two basic operations. Given a counted, unsorted
B-tree containing an unordered list of items, we need to be able to:

\b Split the tree down the middle, giving two valid B-trees as output.

\b Take two valid B-trees and join them together end-to-end, giving
one B-tree containing all the data from tree A followed by the data
from tree B.

This will provide all the operations we need. To unlink a large
section from the middle of a tree, we split it in two places and
then join the outer two parts back together; to link a large section
\e{into} the middle of a tree, we split it at the insertion point,
join the left half on to the left side of the inserted section, and
join the right half on to the right side of the inserted section.

\H{joining} Joining two B-trees together

When you add an element to a B-tree, sometimes it ends up increasing
the size of a leaf node beyond the size limit. When that happens,
you deal with it by splitting the node in two, and transforming the
parent node so that where it previously had a single child pointer,
it now has two child pointers with an element between them. If that
makes the parent node too big as well, you do the same thing again,
and so on until you reach the tree root.

Joining two B-trees is therefore reasonably simple, \e{if} you have
an additional separating element to place in between them. Position
the two trees so that their leaf nodes are at the same level; now
(usually) one tree will be shorter than the other. So you can add
the root of the shorter tree as a sibling of the node next to it in
the taller tree; their common parent gains one extra child pointer
(pointing at the root of the shorter tree), separated from its
neighbour by the additional separating element. If this causes the
node to increase beyond the maximum size, just split it in two and
propagate up to its parent, just as in the ordinary insertion
process.

If the trees were originally the same height, just combine their
root nodes into a single larger root node. You need an extra element
to go in between the rightmost child pointer of the left-hand root
node, and the leftmost child pointer of the right-hand root node;
and again, this is where your separating element comes in. Again, if
the new root is too big to be a single node, split it in two and
create a new root above it.

So it turns out that it's very easy to join two trees together, but
the algorithm requires a spare element to go in the middle. However,
we normally don't have such a spare element: we just have two trees.
This is easily solved, though: we simply start by removing the
leftmost element of the right-hand tree using the ordinary tree
deletion algorithm. Then we just do the join algorithm, as described
above, using the element we just removed as our separator.

\H{splitting} Splitting a B-tree in two

To split a B-tree in two: we are given a tree, and a means of
searching down the tree to find the split point. (In this
application, that will be a numeric position, which we check against
the node counts on the way down; in other situations, we might
perfectly well want to split an ordinary \e{sorted} B-tree in half,
so we might have an ordering-based search criterion. It makes no
difference.)

We start in the simplest possible way. Start at the root node;
decide which of its subtree pointers you are going to descend down;
and saw the node in half at that subtree pointer. The two half-nodes
thus created will \e{each} need a subtree pointer to go on the cut
end, but that's OK because we're about to saw the next node down in
half as well and they can have half each. So descend to the next
node, decide on a split point again, saw that node in half, and put
a pointer to each half in the two halves of the parent node.

Once we finish this searching-and-cutting pass, we will have
successfully separated our tree into two parts at the required
point. However, the result will almost certainly not be a pair of
\e{valid} B-trees; the chances are that many of the nodes on the cut
edges will be below the minimum allowed node size. In fact, if at
any point our search criterion made us descend through the
\e{endmost} subtree pointer in any node, some of those nodes will
have no elements in them whatsoever, just a single subtree pointer!

So now we must make a healing pass down the cut edge of each tree,
to turn it back into a valid B-tree. We can start by throwing away
the root node if it has nothing but a single subtree pointer (which
will happen quite often if we split near one end of the original
tree, since in that case the output trees will almost certainly need
to be of different heights). Keep doing that until we find a real
root node.

One child of that node is on the cut edge, so it may be below the
minimum size. If it is, we solve this using its (valid) neighbour
node. If the neighbour is large, we can move some subtrees over into
the undersized node to make two correctly sized nodes; if the
neighbour is too small and does not have that many subtrees to
spare, we can instead \e{combine} the undersized node with its
neighbour. (And it turns out you can always do at least one of
these: if the neighbour is too large to combine with the undersized
node, then it \e{must} have enough subtrees for redistribution to
give two viable nodes.)

The only interesting case is that combining an undersized node with
its neighbour reduces the number of subtrees of their common parent
by one. Therefore:

\b As we go down, we arrange for each node on the cut edge to be at
least \e{one more than} minimum size, in case its size must drop by
one when we process its child. (This still just about works in all
cases.)

\b If the first non-trivial root node had only two children (recall
that the root node in a B-tree is the only node exempt from the
minimum size limit), and those two children end up having to be
combined, then the root node must be thrown away again and the
combined node is the new root.

Once we have sorted out each node, we descend to its child on the
cut edge, and do the same thing again. Eventually we reach the
bottom of the tree and every node is of valid size. Then we do the
same thing to the cut edge of the other tree, and we're done.

\C{copy-on-write} Cloning trees

The splitting and joining algorithms look as if they make cut and
paste pretty much trivial. You can split a big chunk out of your
editing buffer into a separate cut buffer easily enough; and then
you can \q{paste} it somewhere else by joining it back into the
middle of the editing buffer at a different position.

However, in real life, cut and paste isn't that simple. People often
want to paste the same data more than once; so you can't just link
the cut buffer straight into the editing buffer, because then you
don't still have it to link in again next time. You need to \e{copy}
the cut buffer and link in the copy. Equally, users often want to
press Copy rather than Cut, in which case you have to split the
buffer tree in two places, \e{copy} the middle section, and join all
three back together.

Copying a tree, it would seem, is inherently an O(N) operation;
there's no way you can copy a tree containing megabytes of data
without actually copying all that data.

Or is there?

It turns out that we \e{can} do better than this, by adding another
annotation field to each tree node. This time, the annotation is a
\e{reference count}: it counts the number of pointers to the node,
either from other tree nodes or from the \q{root} field in a tree
header structure. To begin with, of course, all reference counts are
1.

Reference counts are normally used for garbage collection. In this
case, though, I'm going to use them to implement \e{copy-on-write}.
All of the tree-altering algorithms (insertion and deletion, plus
the split and join algorithms described above) will now check the
reference count of a node before attempting to modify it. If they
find that they need to modify a node with a reference count greater
than one, they will not modify it. Instead, they will make a copy of
that node, and use the copy in place of the original. The copy links
to all the same child nodes as the original, so the reference count
in each child must be incremented; and the copied node's parent (or
tree header structure) now links to the copy rather than to the
original, so the reference count in the original must be
decremented. Now we are looking at a node with a reference count of
1, which means nobody else is using it so we can modify it safely.

The effect of this is that it is now a trivial - not merely log-time
but \e{constant}-time - operation to \e{clone} an entire B-tree, no
matter how large. We simply create a new tree header structure; we
point its root field at the root node of the input tree; and we
increment the reference count on that root node.

Once we have cloned a tree like this, we can treat the original and
the clone as if they were entirely independent. If you add an
element to one of them, for example, then a single string of nodes
from the root down to one leaf will be duplicated and modified, but
the rest of the trees will still be held in common. You can split
either tree into lots of little pieces, or join it into the middle
of a larger one, and never affect the data stored in what was once
its clone, because every time you touch a node that the other tree
is depending on, you make your own copy rather than disturbing it.

This allows us to support \e{really} efficient cut and paste in our
hex editor. You select a 200Mb chunk and press Copy; the buffer tree
is split in two places (in log time), the middle section is cloned
(instantly), and the tree is joined back together. You'd hardly know
anything was different - but the cut buffer now contains a clone of
\e{part} of the original buffer, most of which consists of nodes
that are still shared with it. And you can paste in as many copies
as you like of that chunk, still in no worse than O(log N) time. The
best bit is that by the time you've done this a few times and have a
file that's 1600Mb longer than it started out, the hex editor isn't
actually using up 1600Mb more memory, because most of it is in
shared nodes! This technique naturally provides a form of
compression as well as being fast.

\C{lazy-loading} Lazy file loading

In all of the above I have been tacitly assuming that the data
elements stored in my tree are individual bytes. This would be
hideously inefficient if I were using AVL or red-black trees, in
which each node contains precisely one element: for every \e{byte}
of the file being edited, there would be an overhead of two child
pointers, a byte count and a reference count. On a normal 32-bit
machine, that's 20 bytes per node, not counting overhead from the
memory allocator. A factor of twenty is just ridiculous.

B-trees are a bit more flexible, since they can be made to have a
large minimum degree. A B-tree with a minimum node size of (say) 512
can contain up to 1023 bytes of data plus 1024 subtree pointers, and
those 1023 bytes can be packed together in memory so the overhead is
now more like a factor of five. Also, since no node in a B-tree ever
changes its height above ground level, you can just not bother to
allocate space for the 512 NULL child pointers in your leaf nodes,
and since the vast majority of your nodes will \e{be} leaf nodes,
the structure is now closer to being space-efficient.

There are other improvements one could make. For example, there's no
reason why a B-tree really needs to have the \e{same} minimum node
degree at every level; so you could have low-degree nodes everywhere
above the leaf level, and enormous leaf nodes containing 4-8Kb of
file data. You could move to B+ trees in which no actual data
elements were stored anywhere except in the leaf nodes, thus saving
the tiny alignment overheads in the other nodes.

However, there's a better direction to head in. In \k{simple} I
mentioned the idea of using a linked list as the main data
structure, and I said that each element of the linked list would be
a smallish array of file bytes (between size K and 2K). There's no
reason we couldn't do that in our B-tree-based approach: each
element stored in the B-tree is no longer a single byte but a small
block of bytes. It would mean that our element counts no longer
allowed us to jump to the Nth byte, only to the Nth \e{block}; but
we can fix that by replacing the element count with a byte count,
summing the total \e{size} of all the blocks in or below a
particular tree node. Now, given any byte position, we can do a
single log-time search and return a data block plus an offset within
that block.

This technique adds work to all operations. Inserting a byte, for
example, is now done by finding the block it needs to go into,
inserting it in that block, and potentially splitting the block into
two and doing an extra tree operation. Splitting and joining buffers
involves splitting and joining blocks at each end, and checking to
make sure undersized blocks are not created. So what does this
technique buy us, that makes it worthwhile over just storing single
bytes in the B-tree?

The answer is: once we have a block data structure as our tree
element, we can start having different \e{types} of block. In
particular, we can have a type of block which is a placeholder,
containing nothing but a file offset and length. A block of this
type indicates \q{at this point in the tree we have N bytes from
position P in the original file}. Blocks of this type are exempt
from the normal maximum size for normal literal-data blocks.

The effect of this is that we no longer need to read the entire file
into memory when we start up. Instead, we just initialise our tree
trivially, so that it contains nothing but a single placeholder
block, with offset zero and size equal to the initial file size.

Now whenever we need to read data from the tree, and it turns out
the data in question is somewhere in a placeholder block, we must
refer back to the original input file in order to find the data (and
the placeholder block will tell us where in the file to read it
from). So before we do any editing, our hex editor is suddenly a
low-cost hex \e{file viewer}, which just pages back and forth and
refers to the disk all the time.

But as soon as we start altering parts of the file, the placeholder
block gets broken up into smaller blocks, and literal-data blocks
begin to be created in between them. If we cut and paste a section
including a placeholder block, then the tree can end up containing
placeholder blocks in a strange order; it might (for example)
indicate something like \q{the first 192K of the input file; then
the literal bytes 5B 49 A7; then 25K of the input file starting from
position 12345; then 512K of the input file starting from position
204325}.

Now the hex editor \e{looks} as if it's doing exactly the same thing
as it did to begin with. I can page around the original file; I can
insert, delete, overwrite, cut, copy and paste to my heart's
content, and (provided no other process modifies the original file
under our feet) the data I am manipulating will remain consistent at
all times with the editing operations I have performed. But there
wasn't a big delay at startup when the file was loaded in, because
most of it \e{wasn't} loaded in; and if I list the running processes
on my system, the hex editor will not be using memory proportional
to the size of the file. It will only be using memory proportional
to the \e{changes} I've made to the file.

When I save the file, if there are any placeholder blocks remaining
in the buffer tree, the hex editor must write out the new version by
referring to the original. This is the \e{only} remaining operation,
apart from searching, that takes time proportional to the size of
the file. And there are \e{no} remaining operations which take
\e{memory} proportional to the size of the file.

(There is one thing you need to be careful of. Literal data blocks
must be permitted to fall below the minimum size K if there is no
literal block next to them to merge with; in particular, this is
vital if you are writing a binary file from scratch or you would
never be able to give it a size between zero and K. But this raises
the possibility that given a pathological sequence of editing
operations, your data structure might end up being an interleaving
of one-byte literal blocks and one-byte placeholder blocks, giving a
huge space overhead. The simplest solution to this is to impose a
minimum size of 2K on \e{placeholder} blocks, below which you read
the relevant piece of file data and convert them into literal
blocks; then they can be merged with adjacent blocks and the worst
case is no longer terrible.)

We now have a data structure which does pretty much everything you
could reasonably ask a hex editor to be able to do, and does it all
at a reasonable memory cost and (apart from the two genuinely
necessary operations of searching and saving) \e{all} in O(log N)
time.

\C{further} Further directions

The data structure as I have presented it is suitable for use in a
high-performance hex editor with an insert mode.

There are a couple more points worth noting.

\H{further-texted} Conventional text editing

This structure would need only minor modifications to be an
efficient basis for a conventional text editor. In order to do this,
you would need to be able to jump quickly to a particular \e{line}
of the file, which means you'd need a node annotation counting
newlines.

In fact, it's possible to do slightly better than that: we can
devise a more complex node annotation which tracks the effect of an
arbitrary byte sequence on the (line, column) position. Assuming
that a physical tab character always advances the cursor to the next
multiple of 8 spaces, there are three possibilities:

\b A sequence of bytes containing no newlines or tabs simply adds
some number A to the column number, and does not affect the line
number.

\b A sequence of bytes containing no newlines but at least one tab
has the overall effect of adding some number A to the column, and
rounding it up to the next number that is congruent to B mod 8.

\b A sequence of bytes containing at least one newline has the
effect of adding some number A to the \e{line} number, and setting
the column number to a fixed value B.

These three function schemas are closed under composition (i.e.
combining any two of them gives another one). Storing one in each
node of a buffer tree would provide the ability to search directly
to \e{a particular (line, column) position} in a single log-time
search. So the text editor could treat its buffer as a simple
sequence of bytes (or possibly of Unicode characters). This is
superior to treating the buffer as a sequence of lines, because it
removes the distinction between inserting \e{within} a line and
inserting data \e{between} lines. In particular, cut and paste in a
line-based model is fiddly because lines must be spliced together at
each end of the pasted region; but cut and paste in this model is as
trivial as it was in the hex editor - you just cut a sequence of
bytes, paste it somewhere else, and the line/column indexing
automatically keeps up no matter what you do.

The only snag is that if you did this, you would probably no longer
be able to do the trick with placeholder blocks and lazy file
loading; a text editor tends to need to know in advance where all
the newlines are in its buffer, so there would probably be no
alternative to physically loading the file. But in that, at least,
this data structure is no worse than any other.

\H{undo} Supporting undo

An undo function in an editor \e{conceptually} stores a sequence of
previous buffer states, and allows you to return to one of them when
you need to.

Usually, this is not actually implemented by storing copies of the
entire buffer, since that would be ludicrously wasteful of space!
Instead, a journal of changes is kept which allows previous buffer
states to be \e{reconstructed} by reversing the precise changes
made.

One could do that using this data structure, if one wanted to.
However, there's another intriguing option. Since cloning an
arbitrarily large tree is a cheap operation, you could implement
undo by \e{actually} storing a sequence of clones of previous buffer
states! The cost of this would be nothing like as bad as it would
na\u00EF{i}vely appear.

It might still not be ideal, though. Every time you clone a tree and
the two clones diverge, several nodes must be copied, and if each
node contains several blocks of literal data then the cost of
maintaining too many buffer clones might still become prohibitive.
But it's an interesting possibility regardless.

\C{summary} Summary

I've presented a design for a data structure which implements
practically every operation required for a hex editor in O(log N)
time, apart from one or two which genuinely \e{need} to be O(N).

The structure is:

\b A B-tree, each of whose elements is either a small array of 
literal data bytes, or a placeholder block denoting a section of the
unmodified input file.

\b Each B-tree node is annotated with the total byte count of all
the elements in or below that node, allowing a log-time search to
pinpoint any numeric byte position.

\b Those counts provide the only necessary means of navigating the
tree, so there is no need for a sorting criterion.

\b Split and join algorithms make it possible to link and unlink
large chunks from the middle of a buffer at a time.

\b Reference counts implementing copy-on-write allow cloning of
chunks in constant time.

As a result:

\b Inserting or deleting bytes in the file is a log-time operation.

\b Finding a particular byte position is a log-time operation.

\b Cut and paste is always log-time, no matter how large or complex
the chunk of data being moved around.

\b Memory usage grows proportionally to the \e{changes} made to the
file, not the overall file size. (However, memory usage is also
\e{bounded} by a value proportional to the file size, even if you
keep editing and re-editing for ever.)

Searching must still be linear (there's no alternative to actually
reading the data if you need to know anything about its contents),
and saving the modified output file is linear (because you actually
must physically write out that much data), but \e{everything} else
can be done in log time.

I've also sketched a means of converting this into a data structure
for an ordinary text editor, and suggested interesting implications
in the area of undo operations.

\C{ref} References

Donald Knuth's \q{The Art of Computer Programming}
(\W{http://en.wikipedia.org/w/wiki.phtml?title=Special:Booksources&isbn=0201485419}{Addison-Wesley,
ISBN 0201485419}) presents at least some of the same ideas as this
article. Counted and unsorted trees are mentioned in volume 3;
splitting and joining are also described (although Knuth does them
on AVL trees, which are significantly more fiddly to split than
B-trees; you have to cut the tree into lots of little pieces, and
then put them all back together by using the join algorithm
repeatedly).

\q{Tweak}, a hex editor implementing this data structure, can be
downloaded at
\W{http://www.chiark.greenend.org.uk/~sgtatham/tweak/}\cw{http://www.chiark.greenend.org.uk/~sgtatham/tweak/}.

\versionid $Id$