17 Out to Disk

Version 6.1.1¹

Handout:

• SObject.java

17.1 Interacting with Files

This section surveys some of the useful classes for reading and writing "disk" files*, in the java.io package. (* or in Unix/Linux, just files, which could include any kind of device, disk or otherwise)

• For text files:

  • PrintWriter (p. 468, buffered output with println)

    PrintWriter pw = new PrintWriter("drive.txt");
    

  • The File class represents a file path (p.469, "driving directions" to locate a file in the file system):

    File driveFile = new File("/home/james/drive.txt");
    

    Creating the File object does not "open" the file, or even depend on its real existence.
  • The File exists method tells whether the file is actually there on the disk.
  • Portability: for O.S. independence, programs need to abstract from the separator used in file paths (/ in Unix, \ in Windows). Use File.separator

  • A Scanner with a File argument (p. 470), e.g.,

    Scanner scanin = new Scanner(driveFile);
    

    Caution: If you use a file name (a String) instead of a File object, you get a scanner that reads from the string — the file name.)

• Essential recipe for processing files:

  1. Open the file. This is done by instantiating the appropriate class, e.g., PrintWriter or Scanner
  2. Read/write the file as much as desired.

  3. Close the file:

     pw.close();
     scanin.close();
     

     Most files are buffered, and if they are not closed, the last outputs may not be written physically to disk.

• Programs as data: The source code of a program, in a text file, can itself be data for another program, such as a compiler, editor, formatter, etc.

• Binary files (p. 473)

  • ObjectInputStream, ObjectOutputStream read/write objects.
  • FileInputStream, FileOutputStream connect the object streams to files.

  • Serializable interface makes objects writable and readable. If there is a linked structure of objects, then writing the structure to disk requires traversing it and putting it into some "linear" form (kind of like topological sort, except it may be cyclic). This is called serializing the object.

    The Java compiler makes this easy for programmers. Just declare the class implements Serializable. This peculiar interface declares no methods, so there are none to define! The compiler takes care of the details.

• Evaluation of binary files

  Good:

  1. They are efficient to read and write. E.g., numbers are already in binary form, so they don't need to be converted.

     • Makes debugging difficult.
     • You could develop the program and debug it with text I/O, and then after thorough testing convert the I/O to binary. That would alleviate the problem until the last stage.

  2. Easy to create in Java — just declare that classes implement the Serializable interface.

  Bad:

  1. They're binary! They are not easily understood by a person using a text editor. They require the program which can interpret them, or another program that "knows" the same binary file format.

     • Fate of files written in proprietary, closed (secret) binary formats. Microsoft Word ".doc" files, Visual Basic "DOT NOT"

     • Getting even: send somebody a binary attachment that they lack the program to read.

  2. In Java, a new version of the program, or even the same version after recompiling, may be unable to read the saved object file. This can be avoided by declaring a serial version ID. Example: SObject.java

     This seems to work okay in Java 1.6.0, even without the serial version ID, however.

17.2 Compression

(Skip)

17.3 External Sorting

• When we need to sort a file that's too large for RAM (main memory), we resort to external sorting. External = outside of RAM.
• Disk access is very slow (how slow?), whether with a virtual memory swap file or regular file.
• Minimize disk accesses.

• Basic idea of external sorting by a k-way merge sort:

  1. Read in as much data as we have space to sort in RAM.
  2. Sort it; write the sorted data to a temporary disk file, file0.

  3. Repeat until there is no more data to be sorted:

     1. Read in as much data as we have space to sort in RAM.
     2. Sort it; write the sorted data to a temporary disk file, file1.

     3. Merge file0 and file1, writing the result to file2. Note: merge requires very little memory: just the next item in each of the merged files (well, more realistically, there would be a buffer for each file, but anyway it's constant size).

     4. Replace file0 with file2

  4. Deliver file0 as the result; erase other temporary files.

• Any good O.S. will provide a system sort command. Use it for sorting files, unless there's a good reason not to.

  • It's carefully debugged, highly generalized (customizable), and optimized as much as is consistent with its generality.
  • You can probably speed it up with a custom sort, giving up generality, but don't optimize where it won't help!

• Examples of the Unix/Linux sort command This sorts text files (not binary files) in various ways:

  • Sort some.data by alphabetically comparing entire lines, writing the result as sorted.data:

    sort some.data > sorted.data
    

  • Sort it numerically, using numbers at the beginning of each line, replacing the file:

    sort -n some.data > some.data
    

  • Sort in reverse numerical order, writing the result to stdout:

    sort -r -n some.data
    

  • Sort on the second field numerically, resolving ties by sorting on the fourth through fifth fields alphabetically; fields are delimited by space; "k" is for "key":

    sort -k 2,2n -k 4,5 some.data
    

  • Like the preceding, but with fields delimited by commas:

    sort -k 2,2n -k 4,5 -t ',' some.data
    

  • Sort on the 5th through 20th characters of the first field:

    sort -k 1.5,1.20 some.data
    

  • Sort output of program1 and deliver as input to program 2:

    program1 | sort | program2
    

  • For more about the sort command:

    info sort
    

  (More info needed: does 'sort' sort internally when there's sufficient RAM, and externally otherwise? Does it sort externally at all?)

17.4 B-Trees

• Originated by Rudolf Bayer, 1971.
• B is for: balanced? Bayer? Boeing? who knows?

• Anyway, they are balanced search trees, but generalized beyond binary search trees..

  • Motivation is to store large indexes such as in a database system.
  • Index must be stored on disk because of its size.
  • Minimize number of disk accesses, because they're slow.
  • Usually, very branchy, shallow tree structure.
  • Some less branchy cases are also interesting, for smaller search structures (in memory).
• Beautiful concept. Ugly implementation. We will look exclusively at the beautiful part.
• Concept: B-trees are m-way search trees with a few additional requirements.

• An m-way search trees is a generalization of binary search tree (where m = 2):

  • Each node may have up to m children and store up to m − 1 keys and their values.

  • Illustration, with m = 6:

    • k1 through k5 are keys, with values v1 through v5.
    • s1 through s6 are subtrees.

  • Order property:

    • All keys in s1 are < k1;
    • All keys in s2 are > k1, < k2;
    • All keys in s3 are > k2, < k3;
    • …
    • All keys in s_m are > k_m−1.
  • Obviously, a binary search tree is the special case where m = 2.

  • [And is it true that an ordered list is 1-way search tree? Each non-leaf node would have to have one child in such a tree. But no, because each node also would be required to contain 0 keys and 0 values.]

• Search in an m-way search tree is an extension of the search in a binary search tree.

  • At each node, determine where the target key lies in relation to the keys stored in the node, and descend to the appropriate subtree.

• B-trees:

  (Note: our m is Drake's 2 m.)

  • A B-tree of order m is an m-way search tree which either:
    1. Is empty; or
    2. Is non-empty and satisfies:
       1. All leaves are at the same level.
       2. The root, if it is not a leaf, has ≥ 2 children.
       3. All non-leaves (internal nodes) except the root have ≥ ceil(m/2) children.
          • ("ceil(m/2)" means the integer obtained by "rounding up" from the real number m/2, e.g., ceil(4/2) = 2, ceil(5/2) = 3.)
  • We will call a node maximal if it has m subtrees (so, m − 1 keys and values); or minimal if it has ceil(m/2) subtrees (so, ceil(m/2) − 1 keys and values).
  • The reason for these numbers are so that we can split and merge nodes. Roughly speaking, a maximal node can be split into two minimal nodes, or two minimal nodes can be merged into one maximal node. These splits and merges are performed during insertion and deletion, to preserve the B-tree conditions.

B-Tree Insertion

• To insert (k, v):
  1. Apply the search procedure to find the leaf node N into which (k, v) must go.
  2. Insert (k, v) in node N.
  3. If the node N is now too full (i.e., has m keys, entailing m + 1 subtrees), then split it as follows:
     1. The middle key and its value are absorbed into N's parent, P. "Middle" is defined as at ceil(m/2)th position. (The "squeeze" principle applies here: the small size of N exerts pressure, causing the node to burst in two and shooting its middle key out and upwards.)
     2. All keys and values left of the middle (there are ceil(m/2) - 1 of them) are split off into a new node, A.
     3. All keys and values right of the middle are split off into a new node B.
     4. A and B become children of P, and N is destroyed.
  4. If P is now too full, repeat step 3, replacing N by P. (This repetition may continue all the way up to the root, in which case a new root is grown and the tree becomes one level higher.)
• Comments:
  • This is a "two-pass" algorithm: the top-down pass (step 1) finds the point of insertion; the bottom-up pass (steps 3-4) split nodes that are too full.
  • Naturally, such an algorithm is most easily implemented using recursion.
  • Drake presents a "one-pass" version, splitting nodes that are full (have exactly m subtrees) on the way down. This avoids recursion (is that a virtue?), but may split some nodes that don't really need to be split, resulting in excessive disk accesses.
  • All insertions are in already existing leaves. The tree does not grow higher by sprouting new leaves; in fact, it never sprouts any new leaves! It grows higher only by splitting the root.

Example 1: Insertion

Insert 8 into a B-tree of order 5. See the following figures.

(1a) Initial B-tree, before inserting 8.

(1b) After inserting 8 in the leaf (4, 5, 6, 7). The leaf is now too full.

(1c) After splitting the leaf into (4, 5), 6, and (7, 8), and absorbing 6 into its parent. Now the parent node is too full.

(1d) After splitting the parent node into (2, 3), 6, and (9, 10), and absorbing 6 into the root.

(1e) After splitting the root. The tree is now one level higher.

B-Tree Deletion

• Removing data from a B-tree. To remove a key k and its value:

  1. Search for the element E to be deleted. If it is in an internal mode (not a leaf), replace it with a leaf element R, which is either E's inorder successor or its inorder predecessor, as in BST delete. Delete R from its leaf. This reduces all deletions to deletion from a leaf node. This brings up case 2.

  2. If E is in a leaf node N, remove it from the leaf, and then:

     1. If N is the root, we are done. (Write out the new root node to disk, if it is not empty.)

     2. If N is still adequate in size (≥ ceil(m/2) subtrees), we are done. (Write out to disk.)

     3. Otherwise, if N has a left sibling, let L = the nearest left sibling of N. Let P = their parent.

        1. If L is not minimal, perform a "rotation" in which the rightmost key and subtree are absorbed into P, while the key and subtree in P which just precede N descend into N itself. See Figure 2.

           (The "vacuum principle" is at work here: deletion of the key from N creates a vacuum which sucks down a key from P, which creates another vacuum which sucks up a key from L.)

        2. Otherwise (L exists but is minimal), combine ("merge") nodes L and N into a single node, "sucking down" the key in P which is "between" them. See Figure 3.

     4. Otherwise, N has no left sibling, so it must have a right sibling — why? Let R = the nearest right sibling of N, and let P = their parent.

        1. If R is not minimal ...
        2. Otherwise ...

        (The details of d.i and d.ii are omitted; they are symmetric to c.i and c.ii, interchanging "left" and "right".)

• Once again, recursion seems ideal for a down-and-up algorithm.

• There are possible variations.

  • One can combine nodes on the way down to ensure there are no minimal nodes on the path (Drake). This might result in more disk accesses than are strictly necessary.
  • If c.i fails, one can attempt d.i before resorting to c.ii or d.ii. This requires an immediate extra disk access, for the right sibling, but possibly avoids other disk accesses that would result later from combining nodes in case c.ii.

Example 2. Deletion, Case 2.c.i

Delete F from a B-tree of order 5. See figures below.

(2a) Initial B-tree.

(2b) After removal of F. The removal sucks E down to fill the place of F, and sucks D up to take the place of E.

Example 3. Deletion, Case 2.c.ii

Delete F from a B-tree of order 5. See figures below.

(3a) Initial B-tree

(3b) After removing F. The removal sucks E down to fill the place of F. Since (A, D) is so light, it is sucked all the way up and down.

Exercise

From the B-tree (of order 5? order 4?) shown below, delete these values, in order:

1. 50 (easy)
2. 80 (replace with 90 and rotate)
3. 110 (merge with left sibling, then rotate their parent and its right sibling)

Some Interesting Low-Order B-trees

• Although the primary motivation for developing B-trees was for large-scale index structures stored on disk, and hence large values of m, there are interesting special cases with low values of m.

• A B-tree with order ...

  • m = 2 is a binary tree; however, only a full ("perfect") binary tree is a B-tree, so a B-tree of order 2 would not work as a search structure because you could not insert or delete anything.
  • m = 3 is called a 2-3 tree, because each non-leaf node has either 2 or 3 subtrees.
  • m = 4 is called a 2-3-4 tree, because each non-leaf node has either 2, 3, or 4 subtrees.

• Red-black trees as B-trees

  • A red-black tree is 2-3-4 tree in disguise.
  • To put on the disguise, take any 2-3-4 tree, and represent each of its nodes as a binary search tree. (It will be a very small binary tree, of course, with only 1 to 3 nodes.) In each of these 2-3-4 nodes, color the binary tree root black, and its children red. Connect the 2-3-4 node's subtrees in the obvious places.
  • The black condition — that every path from the root of a red-black to an empty subtree passes through the same number of black nodes — follows because all the leaves of a B-tree (2-3-4 tree in particular) are at the same level. Every path from the root to an empty subtree passes through the same number of 2-3-4 tree nodes, and since every such node has one black node in its "internal" binary search tree (namely, the BST root), through the same number of black nodes.
  • The red condition — that every red node has a black parent — follows because the red nodes are the non-root nodes in the binary search trees, and each of them has the root of its binary search tree, which is black, for a parent.

Example 5

Convert a 2-3-4 tree to red-black. See figures below.

(5a) The initial 2-3-4 tree.

                   +-----+
                   |b7   |
                   | \   | 
                   |  r14|
                   +-+---+
        __________/  |    \_______________
       /             |                    \
      +---+          +---+                 +----------+
      |b2 |          |b10|                 |   b18    |
      |\  |          |   |                 |  /   \   |
      | r5|          |   |                 |r16    r21|
      +-+-+          +---+                 +---+--+---+
  ___/ /   \        /     \              _/    |   \  \______
 /    /     \      /       \            /      |    \        \
+--+ +----+ +--+  +----+   +--------+  +---+   +---+ +-----+  +---------+
|b1| |b3  | |b6|  |b8  |   |  b12   |  |b15|   |b17| |b19  |  |  b23    |
|  | | \  | |  |  | \  |   | /  \   |  |   |   |   | | \   |  | /   \   |
|  | |  r4| |  |  |  r9|   |r11  r13|  |   |   |   | |  r20|  |r22   r24|
+--+ +----+ +--+  +----+   +--------+  +---+   +---+ +-----+  +---------+

(5b) After replacing each 2-3-4 node with a small red-black tree.

b7                      b14
 \            or        /
 r14                   r7

             b7
     _______/ \__________________
    /                            \
   b2                            r14
  / \__              ___________/   \____ 
 /     \            /                    \
b1      r5         b10                    b18         
      _/  \     ___/  \_               __/  \_____ 
     /     |   /        \             /           \
     b3    b6  b8        b12         r16           r21       
      \         \       /  \        _/ \        ___/ \____ 
       \         \     /    \      /    \      /          \
        r4        r9   r11   r13   b15   b17   b19         b23
                                                \         _/ \_ 
                                                 \       /     \
                                                 r20    r22   r24

(5c) The red-black tree that remains, after removing the 2-3-4 scaffolding.

Additional References for B-trees

• Brother David Carlson and Brother Isidore Minerd (2009). Software Design Using C++: B-Trees
• Semaphore Corporation (2000). B-tree algorithms
• Wikipedia (2009). B-tree
• Peter Neubauer (1999). B-Trees: Balanced Binary Trees

Footnotes