SQLite4
Check-in [a5186d0b0a]
Not logged in

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

Overview
SHA1 Hash:a5186d0b0ad8032fa1b93a2bcb1b6390003890f4
Date: 2013-11-28 15:23:21
User: dan
Comment:Make a small change to the bt cell formats to accommodate delete keys.
Tags And Properties
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/bt_main.c

1130
1131
1132
1133
1134
1135
1136

1137
1138
1139
1140
1141
1142
1143
....
1144
1145
1146
1147
1148
1149
1150

1151
1152
1153
1154
1155
1156
1157
....
1232
1233
1234
1235
1236
1237
1238

1239
1240
1241
1242
1243
1244
1245
1246
1247

1248
1249
1250
1251
1252
1253
1254
....
1336
1337
1338
1339
1340
1341
1342

1343
1344
1345
1346
1347
1348
1349

1350
1351
1352
1353
1354
1355
1356
1357
1358
....
1411
1412
1413
1414
1415
1416
1417

1418
1419
1420

1421
1422
1423
1424
1425
1426
1427
1428
1429

1430
1431
1432
1433
1434

1435
1436
1437
1438
1439
1440
1441
1442
....
1559
1560
1561
1562
1563
1564
1565



1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
....
1592
1593
1594
1595
1596
1597
1598
1599
1600

1601
1602
1603
1604
1605
1606
1607
....
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829




1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
....
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
....
1871
1872
1873
1874
1875
1876
1877

1878
1879
1880
1881
1882

1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
....
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
  if( nKLocal==0 ){
    /* Type (c) leaf cell. */
    pCell += sqlite4BtVarintGet32(pCell, &nKLocal);
    pKLocal = pCell;
    pCell += nKLocal;
    pCell += sqlite4BtVarintGet32(pCell, &nKOvfl);
    pCell += sqlite4BtVarintGet32(pCell, &nVOvfl);


  }else{
    pKLocal = pCell;
    pCell += nKLocal;
    pCell += sqlite4BtVarintGet32(pCell, &nVLocal);
    if( nVLocal==0 ){
      /* Type (b) */
................................................................................
      pCell += sqlite4BtVarintGet32(pCell, &nVLocal);
      pVLocal = pCell;
      pCell += nVLocal;
      pCell += sqlite4BtVarintGet32(pCell, &nVOvfl);
    }else{
      /* Type (a) */
      pVLocal = pCell;

    }
  }

  pCsr->ovfl.nKey = nKLocal + nKOvfl;
  pCsr->ovfl.nVal = nVLocal + nVOvfl;

  nReq = pCsr->ovfl.nKey + pCsr->ovfl.nVal;
................................................................................
  
  aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
  assert( btCellCount(aData, pgsz)>iCell );
  pCell = btCellFind(aData, pgsz, iCell);
  pCell += sqlite4BtVarintGet32(pCell, &n);

  if( n==0 ){

    pCell += sqlite4BtVarintGet32(pCell, &n);
    pCell += n;
    pCell += sqlite4BtVarintGet32(pCell, &n);
    pCell += sqlite4BtVarintGet32(pCell, &n);
    pOvfl = pCell;
  }else{
    pCell += n;
    pCell += sqlite4BtVarintGet32(pCell, &n);
    if( n==0 ){

      pCell += sqlite4BtVarintGet32(pCell, &n);
      pCell += n;
      pCell += sqlite4BtVarintGet32(pCell, &n);
      pOvfl = pCell;
    }
  }

................................................................................
      pCell += sqlite4BtVarintGet32(pCell, &nK);
      if( nK>0 ){
        pCell += nK;
        pCell += sqlite4BtVarintGet32(pCell, &nV);
      }

      if( nV==0 ){

        rc = btCsrBuffer(pCsr, 1);
        if( rc==SQLITE4_OK ){
          u8 *aBuf = (u8*)pCsr->ovfl.buf.p;
          *ppV = &aBuf[pCsr->ovfl.nKey];
          *pnV = pCsr->ovfl.nVal;
        }
      }else{

        *ppV = pCell;
        *pnV = (nV-1);
      }

#ifndef NDEBUG
      if( rc==SQLITE4_OK ){
        const void *pK; int nK;
        rc = sqlite4BtCsrKey((bt_cursor*)pCsr, &pK, &nK);
        if( rc==SQLITE4_OK ){
................................................................................

static int btCellSize(u8 *pCell, int bLeaf){
  u8 *p = pCell;
  int nKey;

  p += sqlite4BtVarintGet32(p, &nKey);
  if( bLeaf==0 ){

    p += nKey;
    p += 4;
  }else if( nKey==0 ){

    p += sqlite4BtVarintGet32(p, &nKey);
    p += nKey;
    p += sqlite4BtVarintGet32(p, &nKey);
    p += sqlite4BtVarintGet32(p, &nKey);
    p += btOverflowArrayLen(p);
  }else{
    p += nKey;
    p += sqlite4BtVarintGet32(p, &nKey);
    if( nKey==0 ){

      p += sqlite4BtVarintGet32(p, &nKey);
      p += nKey;
      p += sqlite4BtVarintGet32(p, &nKey);
      p += btOverflowArrayLen(p);
    }else{

      p += (nKey-1);
    }
  }

  return (p-pCell);
}

static u8 *btCellFindSize(u8 *aData, int nData, int iCell, int *pnByte){
................................................................................
  const void *pK; int nK;
  const void *pV; int nV;
  u32 pgno;
};

/*
** Return the number of bytes consumed by a cell generated based on *pKV.



*/
static int btKVCellSize(KeyValue *pKV){
  int nByte;
  assert( pKV->eType==KV_CELL || pKV->eType==KV_VALUE );
  if( pKV->eType==KV_CELL ){
    nByte = pKV->nV;
  }else{
    if( pKV->pgno ){
      nByte = sqlite4BtVarintLen32(pKV->nK) + pKV->nK + 4;
    }else{
      nByte = 
        sqlite4BtVarintLen32(pKV->nK) 
        + sqlite4BtVarintLen32(pKV->nV+1)
        + pKV->nV + pKV->nK;
    }
  }
  return nByte;
}

/*
................................................................................
    i = pKV->nV;
    memcpy(aBuf, pKV->pV, i);
  }else{
    i += sqlite4BtVarintPut32(&aBuf[i], pKV->nK);
    memcpy(&aBuf[i], pKV->pK, pKV->nK); i += pKV->nK;

    if( pKV->pgno==0 ){
      i += sqlite4BtVarintPut32(&aBuf[i], pKV->nV+1);
      memcpy(&aBuf[i], pKV->pV, pKV->nV); i += pKV->nV;

    }else{
      btPutU32(&aBuf[i], pKV->pgno);
      i += 4;
    }
  }

  assert( i==btKVCellSize(pKV) );
................................................................................
  int nReq;
  int rc = SQLITE4_OK;

  assert( pKV->pgno==0 && pKV->eType==KV_VALUE );

  /* Check if this is a type (a) cell - one that can fit entirely on a 
  ** leaf page. If so, do nothing.  */
  nReq = sqlite4BtVarintLen32(pKV->nK) + sqlite4BtVarintLen32(pKV->nV);
  nReq += pKV->nK + pKV->nV;
  if( nReq > nMaxSize ){
    int nArraySz = btOverflowArraySz(pgsz, pKV->nK + pKV->nV);
    u8 *pBuf = 0;                 /* Buffer containing formatted cell */
    int nKeyOvfl;                 /* Bytes of key that overflow */
    int nValOvfl;                 /* Bytes of value that overflow */

    /* Check if the entire key can fit on a leaf page. If so, this is a
    ** type (b) page - entire key and partial value on the leaf page, 
    ** overflow pages contain the rest of the value.  */




    nReq = 1 + sqlite4BtVarintLen32(pKV->nK) + pKV->nK 
         + 1 + sqlite4BtVarintLen32(pKV->nV) + nArraySz;

    if( nReq<nMaxSize ){
      /* nSpc is initialized to the amount of space available to store:
      **
      **    * varint containing number of bytes stored locally (nLVal).
      **    * nLVal bytes of content.
      **    * varint containing number of bytes in overflow pages.
      */
................................................................................
      nValOvfl = pKV->nV - nLVal;
    }else{
      /* Type (c) cell. Both the key and value overflow. */
      int nLKey = nMaxSize 
          - 1                                    /* 0x00 byte */
          - sqlite4BtVarintLen32(pgsz)           /* nLKey */
          - sqlite4BtVarintLen32(pKV->nK)        /* nOKey */
          - sqlite4BtVarintLen32(pKV->nV)        /* nVal */
          - nArraySz;                            /* overflow array */

      nValOvfl = pKV->nV;
      nKeyOvfl = pKV->nK - nLKey;
    }

    /* Allocate a pager buffer to store the KV_CELL buffer. Using a pager
................................................................................
      if( nKeyOvfl>0 ){
        *pOut++ = 0x00;
      }
      pOut += sqlite4BtVarintPut32(pOut, nLKey);
      memcpy(pOut, pKV->pK, nLKey);
      pOut += nLKey;
      if( nKeyOvfl==0 ){

        *pOut++ = 0x00;
        pOut += sqlite4BtVarintPut32(pOut, nLVal);
        memcpy(pOut, pKV->pV, nLVal);
        pOut += nLVal;
      }else{

        pOut += sqlite4BtVarintPut32(pOut, nKeyOvfl);
      }
      pOut += sqlite4BtVarintPut32(pOut, nValOvfl);

      rc = btOverflowArrayPopulate(db, &pOut,
          (u8*)(pKV->pK) + nLKey, nKeyOvfl,
          (u8*)(pKV->pV) + nLVal, nValOvfl
      );
      if( rc==SQLITE4_OK ){
        memset(pKV, 0, sizeof(*pKV));
................................................................................
    rc = btBalance(pCsr, bLeaf, 0, 0);
  }
  return rc;
}

static int btSaveAllCursor(bt_db *pDb, BtCursor *pCsr){
  int rc = SQLITE4_OK;            /* Return code */
  bt_cursor *p;                   /* Used to iterate through cursors */

  for(p=pDb->pAllCsr; rc==SQLITE4_OK && p; p=p->pNextCsr){
    if( p->eType==CSR_TYPE_BT ){
      BtCursor *pCsr = (BtCursor*)p;
      if( pCsr->nPg>0 ){
        assert( pCsr->bRequireReseek==0 );
        rc = btCsrBuffer(pCsr, 0);
        if( rc==SQLITE4_OK ){
          assert( pCsr->ovfl.buf.p );
          pCsr->bRequireReseek = 1;
          if( pCsr!=pCsr ) btCsrReleaseAll(pCsr);
        }
      }
    }else{
      /* ?? */
    }

  }

  return rc;
}

static int btFastInsertRoot(bt_db *db, BtDbHdr *pHdr, u32 *piRoot);








>







 







>







 







>









>







 







>







>

|







 







>



>









>





>
|







 







>
>
>












|







 







|
|
>







 







|
<








|
>
>
>
>


<







 







|







 







>





>


|







 







|

|
|
|
|
|
|

|
|
|





<







1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
....
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
....
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
....
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
....
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
....
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
....
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
....
1826
1827
1828
1829
1830
1831
1832
1833

1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848

1849
1850
1851
1852
1853
1854
1855
....
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
....
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
....
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739

2740
2741
2742
2743
2744
2745
2746
  if( nKLocal==0 ){
    /* Type (c) leaf cell. */
    pCell += sqlite4BtVarintGet32(pCell, &nKLocal);
    pKLocal = pCell;
    pCell += nKLocal;
    pCell += sqlite4BtVarintGet32(pCell, &nKOvfl);
    pCell += sqlite4BtVarintGet32(pCell, &nVOvfl);
    nVOvfl -= 1;

  }else{
    pKLocal = pCell;
    pCell += nKLocal;
    pCell += sqlite4BtVarintGet32(pCell, &nVLocal);
    if( nVLocal==0 ){
      /* Type (b) */
................................................................................
      pCell += sqlite4BtVarintGet32(pCell, &nVLocal);
      pVLocal = pCell;
      pCell += nVLocal;
      pCell += sqlite4BtVarintGet32(pCell, &nVOvfl);
    }else{
      /* Type (a) */
      pVLocal = pCell;
      nVLocal -= 2;
    }
  }

  pCsr->ovfl.nKey = nKLocal + nKOvfl;
  pCsr->ovfl.nVal = nVLocal + nVOvfl;

  nReq = pCsr->ovfl.nKey + pCsr->ovfl.nVal;
................................................................................
  
  aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
  assert( btCellCount(aData, pgsz)>iCell );
  pCell = btCellFind(aData, pgsz, iCell);
  pCell += sqlite4BtVarintGet32(pCell, &n);

  if( n==0 ){
    /* Type (c) cell */
    pCell += sqlite4BtVarintGet32(pCell, &n);
    pCell += n;
    pCell += sqlite4BtVarintGet32(pCell, &n);
    pCell += sqlite4BtVarintGet32(pCell, &n);
    pOvfl = pCell;
  }else{
    pCell += n;
    pCell += sqlite4BtVarintGet32(pCell, &n);
    if( n==0 ){
      /* Type (b) cell */
      pCell += sqlite4BtVarintGet32(pCell, &n);
      pCell += n;
      pCell += sqlite4BtVarintGet32(pCell, &n);
      pOvfl = pCell;
    }
  }

................................................................................
      pCell += sqlite4BtVarintGet32(pCell, &nK);
      if( nK>0 ){
        pCell += nK;
        pCell += sqlite4BtVarintGet32(pCell, &nV);
      }

      if( nV==0 ){
        /* Type (b) or (c) cell */
        rc = btCsrBuffer(pCsr, 1);
        if( rc==SQLITE4_OK ){
          u8 *aBuf = (u8*)pCsr->ovfl.buf.p;
          *ppV = &aBuf[pCsr->ovfl.nKey];
          *pnV = pCsr->ovfl.nVal;
        }
      }else{
        /* Type (a) cell */
        *ppV = pCell;
        *pnV = (nV-2);
      }

#ifndef NDEBUG
      if( rc==SQLITE4_OK ){
        const void *pK; int nK;
        rc = sqlite4BtCsrKey((bt_cursor*)pCsr, &pK, &nK);
        if( rc==SQLITE4_OK ){
................................................................................

static int btCellSize(u8 *pCell, int bLeaf){
  u8 *p = pCell;
  int nKey;

  p += sqlite4BtVarintGet32(p, &nKey);
  if( bLeaf==0 ){
    /* Internal page cell */
    p += nKey;
    p += 4;
  }else if( nKey==0 ){
    /* Type (c) cell */
    p += sqlite4BtVarintGet32(p, &nKey);
    p += nKey;
    p += sqlite4BtVarintGet32(p, &nKey);
    p += sqlite4BtVarintGet32(p, &nKey);
    p += btOverflowArrayLen(p);
  }else{
    p += nKey;
    p += sqlite4BtVarintGet32(p, &nKey);
    if( nKey==0 ){
      /* Type (b) cell */
      p += sqlite4BtVarintGet32(p, &nKey);
      p += nKey;
      p += sqlite4BtVarintGet32(p, &nKey);
      p += btOverflowArrayLen(p);
    }else{
      /* Type (a) cell */
      p += (nKey-2);
    }
  }

  return (p-pCell);
}

static u8 *btCellFindSize(u8 *aData, int nData, int iCell, int *pnByte){
................................................................................
  const void *pK; int nK;
  const void *pV; int nV;
  u32 pgno;
};

/*
** Return the number of bytes consumed by a cell generated based on *pKV.
**
** If the KeyValue is not already in KV_CELL form, then assume it will
** be formatted as a type (a) cell.
*/
static int btKVCellSize(KeyValue *pKV){
  int nByte;
  assert( pKV->eType==KV_CELL || pKV->eType==KV_VALUE );
  if( pKV->eType==KV_CELL ){
    nByte = pKV->nV;
  }else{
    if( pKV->pgno ){
      nByte = sqlite4BtVarintLen32(pKV->nK) + pKV->nK + 4;
    }else{
      nByte = 
        sqlite4BtVarintLen32(pKV->nK) 
        + sqlite4BtVarintLen32(pKV->nV+2)
        + pKV->nV + pKV->nK;
    }
  }
  return nByte;
}

/*
................................................................................
    i = pKV->nV;
    memcpy(aBuf, pKV->pV, i);
  }else{
    i += sqlite4BtVarintPut32(&aBuf[i], pKV->nK);
    memcpy(&aBuf[i], pKV->pK, pKV->nK); i += pKV->nK;

    if( pKV->pgno==0 ){
      i += sqlite4BtVarintPut32(&aBuf[i], pKV->nV+2);
      memcpy(&aBuf[i], pKV->pV, pKV->nV); 
      i += pKV->nV;
    }else{
      btPutU32(&aBuf[i], pKV->pgno);
      i += 4;
    }
  }

  assert( i==btKVCellSize(pKV) );
................................................................................
  int nReq;
  int rc = SQLITE4_OK;

  assert( pKV->pgno==0 && pKV->eType==KV_VALUE );

  /* Check if this is a type (a) cell - one that can fit entirely on a 
  ** leaf page. If so, do nothing.  */
  nReq = btKVCellSize(pKV);

  if( nReq > nMaxSize ){
    int nArraySz = btOverflowArraySz(pgsz, pKV->nK + pKV->nV);
    u8 *pBuf = 0;                 /* Buffer containing formatted cell */
    int nKeyOvfl;                 /* Bytes of key that overflow */
    int nValOvfl;                 /* Bytes of value that overflow */

    /* Check if the entire key can fit on a leaf page. If so, this is a
    ** type (b) page - entire key and partial value on the leaf page, 
    ** overflow pages contain the rest of the value.  
    **
    ** This expression uses sqlite4BtVarintLen32() to calculate an upper
    ** bound for the size of the varint that indicates the number of bytes
    ** of the value stored locally.  */
    nReq = 1 + sqlite4BtVarintLen32(pKV->nK) + pKV->nK 
         + 1 + sqlite4BtVarintLen32(pKV->nV) + nArraySz;

    if( nReq<nMaxSize ){
      /* nSpc is initialized to the amount of space available to store:
      **
      **    * varint containing number of bytes stored locally (nLVal).
      **    * nLVal bytes of content.
      **    * varint containing number of bytes in overflow pages.
      */
................................................................................
      nValOvfl = pKV->nV - nLVal;
    }else{
      /* Type (c) cell. Both the key and value overflow. */
      int nLKey = nMaxSize 
          - 1                                    /* 0x00 byte */
          - sqlite4BtVarintLen32(pgsz)           /* nLKey */
          - sqlite4BtVarintLen32(pKV->nK)        /* nOKey */
          - sqlite4BtVarintLen32(pKV->nV+1)      /* nVal */
          - nArraySz;                            /* overflow array */

      nValOvfl = pKV->nV;
      nKeyOvfl = pKV->nK - nLKey;
    }

    /* Allocate a pager buffer to store the KV_CELL buffer. Using a pager
................................................................................
      if( nKeyOvfl>0 ){
        *pOut++ = 0x00;
      }
      pOut += sqlite4BtVarintPut32(pOut, nLKey);
      memcpy(pOut, pKV->pK, nLKey);
      pOut += nLKey;
      if( nKeyOvfl==0 ){
        /* Type (b) cell */
        *pOut++ = 0x00;
        pOut += sqlite4BtVarintPut32(pOut, nLVal);
        memcpy(pOut, pKV->pV, nLVal);
        pOut += nLVal;
      }else{
        /* Type (c) cell */
        pOut += sqlite4BtVarintPut32(pOut, nKeyOvfl);
      }
      pOut += sqlite4BtVarintPut32(pOut, nValOvfl + (nKeyOvfl>0));

      rc = btOverflowArrayPopulate(db, &pOut,
          (u8*)(pKV->pK) + nLKey, nKeyOvfl,
          (u8*)(pKV->pV) + nLVal, nValOvfl
      );
      if( rc==SQLITE4_OK ){
        memset(pKV, 0, sizeof(*pKV));
................................................................................
    rc = btBalance(pCsr, bLeaf, 0, 0);
  }
  return rc;
}

static int btSaveAllCursor(bt_db *pDb, BtCursor *pCsr){
  int rc = SQLITE4_OK;            /* Return code */
  bt_cursor *pIter;               /* Used to iterate through cursors */

  for(pIter=pDb->pAllCsr; rc==SQLITE4_OK && pIter; pIter=pIter->pNextCsr){
    if( pIter->eType==CSR_TYPE_BT ){
      BtCursor *p = (BtCursor*)pIter;
      if( p->nPg>0 ){
        assert( p->bRequireReseek==0 );
        rc = btCsrBuffer(p, 0);
        if( rc==SQLITE4_OK ){
          assert( p->ovfl.buf.p );
          p->bRequireReseek = 1;
          if( p!=pCsr ) btCsrReleaseAll(p);
        }
      }
    }else{
      /* ?? */
    }

  }

  return rc;
}

static int btFastInsertRoot(bt_db *db, BtDbHdr *pHdr, u32 *piRoot);

Changes to www/bt.wiki

538
539
540
541
542
543
544
545

546
547
548
549
550
551
552
553
...
559
560
561
562
563
564
565
566

567
568
569
570
571
572
573
that use overflow pages for the value only, and (c) cells that use overflow
pages for the key and value.

<p>Cell type (a):
<ul>
  <li> Number of bytes of the entries key (nKey), as a varint.
  <li> nKey bytes of key data.
  <li> Number of bytes in entries value plus one (nValue+1), as a varint.

  <li> nValue bytes of value data.
</ul>

<p>Cell type (b):
<ul>
  <li> Number of bytes in entries key (nKey), as a varint.
  <li> nKey bytes of key data.
  <li> Single 0x00 byte.
................................................................................
<p>Cell type (c):
<ul>
  <li> Single 0x00 byte.
  <li> Number of bytes of the entries key (nLocalKey) stored locally, 
       as a varint.
  <li> nLocalKey bytes of key data.
  <li> Number of bytes of the entries key stored on overflow pages, as a varint.
  <li> Number of bytes in the entries value, as a varint.

</ul>

<p>Cell types (b) and (c) are followed by an array of pointers to overflow
pages. The overflow data for a single entry is distributed between up to 16
"direct" overflow pages and a single overflow tree. A direct overflow page
is just that - a pointer to an overflow page that contains data. An overflow
"tree" is a tree structure where leaves contain overflow data and nodes 







|
>
|







 







|
>







538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
...
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
that use overflow pages for the value only, and (c) cells that use overflow
pages for the key and value.

<p>Cell type (a):
<ul>
  <li> Number of bytes of the entries key (nKey), as a varint.
  <li> nKey bytes of key data.
  <li> Number of bytes in entries value plus one (nValue+2), as a varint. Or,
       for a delete key, a single 0x01 byte.
  <li> Unless this is a delete key, nValue bytes of value data.
</ul>

<p>Cell type (b):
<ul>
  <li> Number of bytes in entries key (nKey), as a varint.
  <li> nKey bytes of key data.
  <li> Single 0x00 byte.
................................................................................
<p>Cell type (c):
<ul>
  <li> Single 0x00 byte.
  <li> Number of bytes of the entries key (nLocalKey) stored locally, 
       as a varint.
  <li> nLocalKey bytes of key data.
  <li> Number of bytes of the entries key stored on overflow pages, as a varint.
  <li> Number of bytes in the entries value plus one (nValue+1), as a varint.
       Or, for a delete key, a single 0x00 byte.
</ul>

<p>Cell types (b) and (c) are followed by an array of pointers to overflow
pages. The overflow data for a single entry is distributed between up to 16
"direct" overflow pages and a single overflow tree. A direct overflow page
is just that - a pointer to an overflow page that contains data. An overflow
"tree" is a tree structure where leaves contain overflow data and nodes