Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Changes to src/btree.c.

     5      5   ** a legal notice, here is a blessing:
     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12         -** $Id: btree.c,v 1.342 2007/03/26 22:05:01 drh Exp $
           12  +** $Id: btree.c,v 1.343 2007/03/27 14:05:23 drh Exp $
    13     13   **
    14     14   ** This file implements a external (disk-based) database using BTrees.
    15     15   ** For a detailed discussion of BTrees, refer to
    16     16   **
    17     17   **     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
    18     18   **     "Sorting And Searching", pages 473-480. Addison-Wesley
    19     19   **     Publishing Company, Reading, Massachusetts.
    20     20   **
    21     21   ** The basic idea is that each page of the file contains N database
    22     22   ** entries and N+1 pointers to subpages.
    23     23   **
    24     24   **   ----------------------------------------------------------------
    25         -**   |  Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N) | Ptr(N+1) |
           25  +**   |  Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) |
    26     26   **   ----------------------------------------------------------------
    27     27   **
    28     28   ** All of the keys on the page that Ptr(0) points to have values less
    29     29   ** than Key(0).  All of the keys on page Ptr(1) and its subpages have
    30     30   ** values greater than Key(0) and less than Key(1).  All of the keys
    31         -** on Ptr(N+1) and its subpages have values greater than Key(N).  And
           31  +** on Ptr(N) and its subpages have values greater than Key(N-1).  And
    32     32   ** so forth.
    33     33   **
    34     34   ** Finding a particular key requires reading O(log(M)) pages from the 
    35     35   ** disk where M is the number of entries in the tree.
    36     36   **
    37     37   ** In this implementation, a single file can hold one or more separate 
    38     38   ** BTrees.  Each BTree is identified by the index of its root page.  The
    39     39   ** key and data for any entry are combined to form the "payload".  A
    40     40   ** fixed amount of payload can be carried directly on the database
    41     41   ** page.  If the payload is larger than the preset amount then surplus
    42     42   ** bytes are stored on overflow pages.  The payload for an entry
    43     43   ** and the preceding pointer are combined to form a "Cell".  Each 
    44         -** page has a small header which contains the Ptr(N+1) pointer and other
           44  +** page has a small header which contains the Ptr(N) pointer and other
    45     45   ** information such as the size of key and data.
    46     46   **
    47     47   ** FORMAT DETAILS
    48     48   **
    49     49   ** The file is divided into pages.  The first page is called page 1,
    50     50   ** the second is page 2, and so forth.  A page number of zero indicates
    51     51   ** "no such page".  The page size can be anything between 512 and 65536.
................................................................................
   119    119   **
   120    120   **   OFFSET   SIZE     DESCRIPTION
   121    121   **      0       1      Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
   122    122   **      1       2      byte offset to the first freeblock
   123    123   **      3       2      number of cells on this page
   124    124   **      5       2      first byte of the cell content area
   125    125   **      7       1      number of fragmented free bytes
   126         -**      8       4      Right child (the Ptr(N+1) value).  Omitted on leaves.
          126  +**      8       4      Right child (the Ptr(N) value).  Omitted on leaves.
   127    127   **
   128    128   ** The flags define the format of this btree page.  The leaf flag means that
   129    129   ** this page has no children.  The zerodata flag means that this page carries
   130    130   ** only keys and no data.  The intkey flag means that the key is a integer
   131    131   ** which is stored in the key size entry of the cell header rather than in
   132    132   ** the payload area.
   133    133   **