Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | (no comment) |
|---|---|
| Downloads: | Tarball | ZIP archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
906aef1f58bcc3470e598e8cde1c66b8 |
| User & Date: | dan 2008-07-22 17:22:17.000 |
Context
|
2008-07-22
| ||
| 17:24 | Move fileio.html and fileformat.html from the other repository to this one. (check-in: 861079d8dc user: dan tags: trunk) | |
| 17:22 | (no comment) (check-in: 906aef1f58 user: dan tags: trunk) | |
| 17:20 | Added the "appreq.html" document. (check-in: ad008410e6 user: drh tags: trunk) | |
Changes
Changes to pages/fileformat.in.
|
| > > > > > > > > > | > > > > > > > > > | > | | < < | > > > > | > > > > > > > > > > > > > > > > > > > > > > | > | < | > > | | > > > | > > > > > > > > | < < > > > > > | > > > > > > > > > | > > | | > > > | > > > > | > > > > > | > | | | > > > | > > > > | < > > > > > > > > | > > > > > > | > > > | > > > | > | > > | > > > | > > > | > > > | > > > > > > | > > | | | > > > > > | > > > > > > > > > | < | > > > > | > > > > | > > > > | > > > < > > > | | > > > | > > > > > | > > > | | | > > > | > > > > > | > > > > | < < > > > > > > > > > > > | > > > | > > > > | > > > > | | > > > > | | < > > > | > > > | | > | | > | | | > > > > > | > > > > > > > > > | > > | > > > > > | < > > > > > > > > | | > | > > > > | > > > | < > > | > > > > > > > > > | | > | < > > > > | > > > > > | < > > | < > > | | > > > > | | | | | | | > > > > > > > | > > > > | > > > > | > > > > | | | > > > > > | > > > | | > > > > > > > | > > > > > | > > > > > > > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > | > > > > > > > | > > > > > > > | < > > | > > > > > > > | > > > > | > | < < < < < > > > > | > > > > > > > > > > > > > | > > > > > > > > > > > > > | | > > > | < > > > > > > > > > > > | > > | | > | > > > > > > > | | > > | > | > > > > > > > > > > > > > | > | > | | > | > > | | > > > | > > > > > > > > > > > > > > > > | > > > > | | > > > | > > > > | > > > | > > | > > | > > > > | > > > > | > > > > | < > > > > > > | | < < > > | < < < > | > | | > > | < > > > > > > > > > > > > > > > > | | > > > > > | > > > > > > > | > | < < < < | > > > | < < < > > | > > > > > > > > | | | > | > | > > > > > > > > > > > > | > > > > > > > > > > > > > > > > > > > > > > > > > | < > > > > > > > > | | > > > | | | > > | < > | < < | | | > > > > | > | > > > > > > > > > | > | | > > > > > | > | > > | > | > > | | > > > | > > > > | > > > | < > > > > | | > > > > > > > | > | > > > > > > | | | > > > > | > > > > > > > > > > | > > > > > > > > > > > > > > > > > > > > > | > > > > > | > > > | | > > > < | | | | | > | > | > > > > > | > > > > | > > > | > > > > > > | > > | > > > > > | > > > > > > > > | < < < > > | > | > | > > > > > > > > > > > > | > > > > > > > > > > > | > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | > > > > > > > > > > > > > > | > > > > > > > > > | > > > | > > > > > | > > > > > > > > | | | > > > | | | > | | > > > > > | > > > > > > > > > > > | > | > > | > > | > > | > > | < < < < > > | > > | < < < > > | < < > > > > > > > > > > > > > > > > > > > > > > > > > | > > > > > > | < < | > > > > > > > > > > | | | > | | < | | | | > | > > > | | > > > | < > > > | | < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | > > > > | > > > > | > > > > > > > > > > > > > > > > < < | < | | | | | | | | | | | > > | > > > > > > > > > > > > > > > > > > > > > > > > | | | > > > > > > | > | | > > > > > > | > > > | > > > | < < < < < > > > > > > > > > > | | < > > > > > > > | > > | | < > > > > > > | > > > > > > | > > | | > > > > | > > > > | > > > > > > | > | > > > | < > > > > > > > > > > > > > > | < > | > > > > > > > > > > | > | > > > > > > | > | > > | < > | > | | > > > > > > | | > | > > | | > > | > > > > | < > > > > > > > > > > | | | | | | | | | | | | | > > > > > > | > > > > > | > > > > > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | > > | < < > > > > | | > > > > | < > > > > > > > > > > > > | < | > > | > > > > > > > > | < < < > > | | > > > > | > > > > | > > | | > | | > > > > > | > > > > | | > > > > | > > > > > > > > | | > > > > > > > | > | > > > > > > > | | | | | | | | > | | > > > > > > > > > > > > > > > > > > > > > > > | > > > > > > > > > > > > | > > > > > | > > > | | > > > | < > | > | | | > > > > | > | | > > > | > | > > > > | > > > > > > | < > > > > > > | > > > | > | > > > | > > | | < > > | > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | | > | > > > | < < < < | | | | | < | > > > > > > > > | > > | > > > | > > > > | > > > > > | | > > > > > > > | > > > > > > | > > | > > > > | > > > > > > | | > > > > | < > | < > | > > > > | | | > | > > > > | | > > > > > > > > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | < | > > > > > > > > > > > > > > > > > > > > | > > > | < | > > > > > | | | > | > > | > > > | > > > > > > > > | > | > > > | > > > > > > > > | > > > > > > > > > > > > | < < < > > > > | | > > > > | < < > > > > > > > > > > > | < > > > > > > > > > | > > > > > > > > > > < > > > | | > > > > > > > | > > > > > > > | | > > > > > | | < < < < > | < < > > > | > | > > > > > > > > > > > > > > > > > > > > > > > | > > > > > > | > > | > > | | < < > > > > > > > > > | > > > > | > > > > | > > > | > > > > | > > > | > > > > > > > > > > > > > > > > | > > > > | > > > > > > > > | > | < > > | < > > > | > > > > > > > > | > > > > > | > | < | | | | | | > > > > > > | > > > > > > > > > > > > > > > > > | | > > > > > > > > > > > > > > > > > > > > > > > > > | > | < > > > > > > > > > > > > | | < > > > > > > > > > > > > > > > > > > | < < > > > > > > > > > > > | < < < < < > | | < < < > > > > > > > | | | > > | > > > > > > > > > > > > > > > > > > > > | > > > | < < < | | < > > > | | < > > > > > > | > > | | > > > > > > > > > > > | < | | | > > > > > > > > > > > > > | > > > > > > > > | > > > > > > > > | > > > > | > > > | > > > > > | | > > > > > > > > > > | > > > | > > | | > | > > > > > > > > > > > > > > > | < < > > > > | < | > > > > > > > > > > | > > | > | > > > | < < > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | < > > > | < > | > > | < < > | | > | < < > | < < < < < > > > > > > > > > > | > > > > > > > > > > > > | > > > > > > | | < > > | > | > > > > > | > > > > | > > > > > | > > > > > > > > > > > > > > > > > > > | > > > | > | < < > > > > > > > > > > > > > > | | < < < < < < < < < | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 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 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 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 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 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 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 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 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 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 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 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 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 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 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 |
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<link type="text/css" rel="stylesheet" href="images/fileformat/rtdocs.css">
<script type="text/javascript" src=images/fileformat/rtdocs.js></script>
</head>
<body>
<div id=document_title>SQLite Database File Format</div>
<div id=toc_header>Table Of Contents</div>
<div id=toc>
<b>Javascript is required for some features of this document, including
table of contents, figure numbering and internal references (section
numbers and hyper-links.
</b>
</div>
<!-- End of standard rt docs header -->
<h1>Document Overview</h1>
<h2>Scope and Purpose</h2>
<p>
This document is designed to serve two purposes:
<ul>
<li>to provide an engineering guide to the file format used by SQLite, and
<li>to provide system requirements specifying the behaviour of the SQLite
software modules responsible for creating and manipulating the
formatted database files.
</ul>
<p>
Exactly how the database file is created and safely updated on the
persistent media is outside the scope of this document. As such no
mention of journal or statement files is made. Database transactions
are referred to only with respect to those file manipulation operations
(i.e. change-counter management and database reorganization in auto-vacuum
mode) that occur once per transaction. Here we are concerned solely with
the arrangement of bytes in the database file, not the interactions between
the SQLite library and the VFS (Virtual File System) interface.
<p>
Similarly, the various interfaces and SQL language features that may
be used to manipulate the contents of a database are not dealt with
here. This document describes the effect of various operations
on the database, such as creating a table or inserting a new record.
The myriad of ways that these operations or sets of these operations
may be achieved using SQLite are dealt with elsewhere.
<p class=todo>
Add references to the documents that do describe these things. One other
document will concentrate on the pager module and the way it uses the VFS
interface to safely create and update database files. The other will be
the document that describes the supported SQL language and capabilities.
<h2>Document and Requirements Organization</h2>
<p>
Section <cite>sqlite_database_files</cite> contains simple
requirements describing the relationship between SQLite and the
definition of a <i>well-formed SQLite database file</i>.
<p>
Section <cite>database_file_format</cite> describes the various fields
and sub-structures that make up the SQLite database file format.
<p>
Section <cite>database_file_manipulation</cite> describes the way in
which these fields and data structures are created, initialized and
updated.
<h2>Glossary</h2>
<table id=glossary>
<tr><td>Auto-vacuum last root-page<td>
A page number stored as 32-bit integer at byte offset 52 of the
database file header (see section <cite>file_header</cite>). In
an auto-vacuum database, this is the numerically largest
<i>root-page</i> number in the database. Additionally, all pages that
occur before this page in the database are either B-Tree <i>root
pages</i>, <i>pointer-map pages</i> or the <i>locking page</i>.
<tr><td>Auto-vacuum database <td>
Each database is either an auto-vacuum database or a non auto-vacuum
database. Auto-vacuum databases feature pointer-map pages (section
<cite>pointer_map_pages</cite>) and have a non-zero value stored
as a 4-byte big-endian integer at offset 52 of the file header (section
<cite>file_header</cite>).
<tr><td>B-Tree <td>
A B-Tree is a tree structure optimized for offline storage. The table
and index data in an SQLite database file is stored in B-Tree
structures.
<tr><td>B-Tree cell <td>
Each database page that is part of a B-Tree structure contains zero
or more B-Tree cells. A B-Tree cell contains a single B-Tree key value
(either an integer or database record) and optionally an associated
database record value.
<tr><td>B-Tree page <td>
A database page that is part of a B-Tree tree structure (not an
overflow page).
<tr><td>(B-Tree) page header <td>
The 8 (leaf pages) or 12 (internal node pages) byte header that
occurs at the start of each B-Tree page.
<tr><td>Cell content area <td>
The area within a B-Tree page in which the B-Tree cells are stored.
<tr><td>(Database) text encoding <td>
The text encoding used for all text values in the database file. One
of UTF-8, big-endian UTF-16 and little-endian UTF-16. The database
text encoding is defined by a 4 byte field stored at byte offset
56 of the database file header (see section <cite>file_header</cite>).
<tr><td>(Database) file header <td>
The first 100 bytes of an SQLite database file constitute the
database file header.
<tr><td>(Database) page size <td>
An SQLite database file is divided into one or more pages of
page-size bytes each.
<tr><td>Database record <td>
A database record is a blob of data containing the serialized
representation of an ordered list of one or more SQL values.
<tr><td>Database record header <td>
The first part of each database record contains the database
record header. It encodes the types and lengths of values stored
in the record (see section <cite>record_format</cite>).
<tr><td>Database record data area <td>
Following the database record header in each database record is
the database record data area. It contains the actual data (string
content, numeric value etc.) of all values in the record
(see section <cite>record_format</cite>).
<tr><td>Default pager cache size <td>
A 32-bit integer field stored at byte offset 48 of the database file
header (see section <cite>file_header</cite>).
<tr><td style="white-space:nowrap">(Database) usable page size <td>
The number of bytes of each database page that is usable. This
is the page-size less the number of bytes left unused at the end
of each page. The number of bytes left unused is governed by the
value stored at offset 20 of the file header (see section
<cite>file_header</cite>).
<tr><td>File format read version <td>
Single byte field stored at byte offset 20 of the database file header
(see section <cite>file_header</cite>).
<tr><td>File format write version <td>
Single byte field stored at byte offset 19 of the database file header
(see section <cite>file_header</cite>).
<tr><td>File change counter <td>
A 32-bit integer field stored at byte offset 24 of the database file
header (see section <cite>file_header</cite>). Normally, SQLite
increments this value each time it commits a transaction.
<tr><td>Fragment <td>
A block of 3 or less bytes of unused space within the cell content
area of a B-Tree page.
<tr><td>Free block <td>
A block of 4 or more bytes of unused space within the cell content
area of a B-Tree page.
<tr><td>Free block list <td>
The linked list of all free blocks on a single B-Tree page (see
section <cite>index_btree_page_format</cite>).
<tr><td>Free page <td>
A page that is not currently being used to store any database data
or meta data. Part of the free-page list.
<tr><td>Free page list <td>
A data structure within an SQLite database file that links all the
free-pages together.
<tr><td>Index B-Tree <td>
One of two variants on the B-Tree data structure used within SQLite
database files. An index B-Tree (section <cite>index_btrees</cite>)
uses database records as keys.
<tr><td>Incremental Vacuum flag <td>
A 32-bit integer field stored at byte offset 64 of the database file
header (see section <cite>file_header</cite>). In auto-vacuum
databases, if this field is non-zero then the database is not
automatically compacted at the end of each transaction.
<tr><td>Locking page <td>
The database page that begins at the 1GB (2<sup>30</sup> byte)
boundary. This page is always left unused.
<tr><td>Logical database <td>
An SQLite database file is a serialized representation of a logical
database. A logical database consists of the SQL database schema,
the content of the various tables in the database, and assorted
database properties that may be set by the user (auto-vacuum,
page-size, user-cookie value etc.),
<tr><td>Non-auto-vacuum database <td>
Any database that is not an auto-vacuum database. A non-auto-vacuum
database contains no pointer-map pages and has a zero value stored
in the 4-byte big-endian integer field at offset 52 of the database
file header (section <cite>file_header</cite>).
<tr><td>Overflow chain <td>
A linked list of overflow pages across which a single (large)
database record is stored (see section
<cite>overflow_page_chains</cite>).
<tr><td>Overflow page <td>
If a B-Tree cell is too large to store within a B-Tree page, a
portion of it is stored using a chain of one or more overflow pages
(see section <cite>overflow_page_chains</cite>).
<tr><td>Pointer-map page <td>
A database page used to store meta data only present in auto-vacuum
databases (see section <cite>pointer_map_pages</cite>).
<tr><td>Right child page <td>
Each internal B-Tree node page has one or more child pages. The
rightmost of these (the one containing the largest key values) is
known as the right child page.
<tr><td>Root page <td>
A root page is a database page used to store the root node of a
B-Tree data structure.
<tr><td>Schema layer file format <td>
An integer between 1 and 4 stored as a 4 byte big-endian integer at
offset 44 of the file header (section <cite>file_header</cite>).
Certain file format constructions may only be present in databases
with a certain minimum schema layer file format value.
<tr><td>Schema table <td>
The table B-Tree with root-page 1 used to store database records
describing the database schema. Accessible as the "sqlite_master"
table from within SQLite.
<tr><td>Schema version <td>
A 32-bit integer field stored at byte offset 40 of the database file
header (see section <cite>file_header</cite>). Normally, SQLite
increments this value each time it modifies the databas schema.
<tr><td>Table B-Tree <td>
One of two variants on the B-Tree data structure used within SQLite
database files. A table B-Tree (section <cite>table_btrees</cite>)
uses 64 bit integers as key values and stores an associated database
record along with each key value.
<tr><td>User cookie <td>
A 32-bit integer field stored at byte offset 60 of the database file
header (see section <cite>file_header</cite>). Normally, SQLite
increments this value each time it modifies the databas schema.
<tr><td>Variable Length Integer <td>
A format used for storing 64-bit signed integer values in SQLite
database files. Consumes between 1 and 9 bytes of space, depending
on the precise value being stored.
<tr><td>Well formed database file <td>
An SQLite database file that meets all the criteria laid out in
section <cite>database_file_format</cite> of this document.
</table>
<h1 id=sqlite_database_files>SQLite Database Files</h1>
<p>
The bulk of this document, section <cite>database_file_format</cite>,
contains the definition of a <i>well-formed SQLite database file</i>.
SQLite is required to create database files that meet this definition.
<p class=req id=FF0010>
The system shall ensure that at the successful conclusion of a
database transaction the contents of the database file constitute
a <i>well-formed SQLite database file</i>.
<p>
Additionally, the database file should contain a serialized version
of the logical database produced by the transaction. For all but the
most trivial logical databases, there are many possible serial
representations.
<p class=req id=FF0020>
The system shall ensure that at the successful conclusion of a
database transaction the contents of the database file are a valid
serialization of the contents of the logical SQL database produced
by the transaction.
<p>
Section <cite>database_file_manipulation</cite> contains requirements
describing in more detail the way in which SQLite manipulates the
fields and data structures described in section
<cite>database_file_format</cite> under various circumstances. These
requirements are to a certain extent derived from the requirements
in this section.
<h1 id=database_file_format>Database File Format Details</h1>
<p>
This section describes the various fields and sub-structures that make up
the format used by SQLite to serialize a logical SQL database.
<p>
This section does not contain requirements governing the behaviour of any
software system. Instead, along with the plain language description of the
file format are a series of succinct, testable statements describing the
properties of "well-formed SQLite database files". Some of these
statements describe the contents of the database file in terms of the
contents of the logical SQL database that it is a serialization of. e.g.
"For each SQL table in the database, the database file shall...".
The contents and properties of a logical database
include:
<ul>
<li>Whether or not the database is an auto-vacuum database, and if
so whether or not incremental-vacuum is enabled,
<li>The configured page-size of the database,
<li>The configured text-encoding of the database,
<li>The configured user-cookie value,
<li>The set of database tables, indexs, triggers and views that make
up the database schema and their properties, and
<li>The data (rows) inserted into the set of database tables.
</ul>
<p class=todo>
This concept of a logical database should be defined properly
in some requirements document so that it can be referenced from
here and other places. The definition will be something like the
list of bullet points above.
<p>
A well-formed SQLite database file is defined as a file for which
all of the statements itemized as requirements within this section
are true. <span class=todo>mention the requirements numbering scheme
here.</span> A software system that wishes to interoperate with other
systems using the SQLite database file format should only ever
output well-formed SQLite databases. In the case of SQLite itself,
the system should ensure that the database file is well-formed at
the conclusion of each database transaction.
<h2 id="fileformat_overview">File Format Overview</h2>
<p>
A B-Tree is a data structure designed for offline storage of a set of
unique key values. It is structured so as to support fast querying
for a single key or range of keys. As implemented in SQLite, each
entry may be associated with a blob of data that is not part of the
key. For the canonical introduction to the B-Tree and its variants,
refer to reference <cite>ref_comer_btree</cite>. The B-Tree
implementation in SQLite also adopts some of the enhancements
suggested in <cite>ref_knuth_btree</cite>
<p>
An SQLite database file contains one or more B-Tree structures. Each
B-Tree structure stores the data for a single database table or
index. Hence each database file contains a single B-Tree to store
the contents of the <i>sqlite_master</i> table, and one B-Tree
for each database table or index created by the user. If the database
uses auto-increment integer primary keys, then the database file
also contains a B-Tree to store the contents of the automatically
created <i>sqlite_sequence</i> table.
<p>
SQLite uses two distinct variants of the B-Tree structure. One variant,
hereafter refered to as a "table B-Tree" uses signed 64-bit integer
values for keys. Each entry has an associated variable length blob of
data used to store a database record (see section
<cite>record_format</cite>). Each SQLite database file contains one
table B-Tree for the schema table and one table B-Tree for each
additional database table created by the user.
<p>
A database record is a blob of data containing an ordered list of
SQL values (integers, real values, NULL values, blobs or strings).
For each row in each table at the SQL level, there is an
entry in the corresponding table B-Tree structure in the file. The
entry key is same as the SQL "rowid" or "integer primary key" field
of the table row. The associated database record is made up of the
row's column values, in declaration (CREATE TABLE) order.
<p>
The other B-Tree variant used by SQLite, hereafter an "index B-Tree"
uses database records (section <cite>record_format</cite>) as keys.
For this kind of B-Tree, there is no additional data associated with
each entry. SQLite databases contain an index B-Tree for each database
index created by the user. Database indexes may be created by CREATE
INDEX statements, or by UNIQUE or PRIMARY KEY (but not INTEGER PRIMARY
KEY) clauses added to CREATE TABLE statements.
<p>
Index B-Tree structures contain one entry for each row in the
associated table at the SQL level. The database record used as the
key consists of the row's value for each of the indexed columns in
declaration (CREATE INDEX) order, followed by the row's "rowid" or
"integer primary key" column value.
<p>
For example, the following SQL script:
<pre>
CREATE TABLE t1(a INTEGER PRIMARY KEY, b, c, d);
CREATE INDEX i1 ON t1(d, c);
INSERT INTO t1 VALUES(1, 'triangle', 3, 180, 'green');
INSERT INTO t1 VALUES(2, 'square', 4, 360, 'gold');
INSERT INTO t1 VALUES(3, 'pentagon', 5, 540, 'grey');
...</pre>
<p>
Creates a database file containing three B-Tree structures: one table
B-Tree to store the <i>sqlite_master</i> table, one table B-Tree to
store table "t1", and one index B-Tree to store index "i1". The
B-Tree structures created for the user table and index are populated
as shown in figure <cite>figure_examplepop</cite>.
<center><img src="images/fileformat/examplepop.gif">
<p><i>Figure <span class=fig id=figure_examplepop></span> - Example B-Tree Data.</i>
</center>
<h2>Global Structure</h2>
<p>
The following sections and sub-sections describe precisely the format
used to house the B-Tree structures within an SQLite database file.
<h3 id="file_header">File Header</h3>
<p>
Each SQLite database file begins with a 100-byte header. The header
file consists of a well known 16-byte sequence followed by a series of
1, 2 and 4 byte unsigned integers. All integers in the file header (as
well as the rest of the database file) are stored in big-endian format.
<p>
The well known 16-byte sequence that begins every SQLite database file
is:
<pre>
0x53 0x51 0x4c 0x69 0x74 0x65 0x20 0x66 0x6f 0x72 0x6d 0x61 0x74 0x20 0x33 0x00</pre>
<p>
Interpreted as UTF-8 encoded text, this byte sequence corresponds
to the string "SQLite format 3" followed by a nul-terminator byte.
<p>
The 1, 2 and 4 byte unsigned integers that make up the rest of the
database file header are described in the following table.
<table class=striped>
<tr><th>Byte Range <th>Byte Size <th width=100%>Description
<tr><td>16..17 <td>2<td>
Database page size in bytes. See section
<cite>pages_and_page_types</cite> for details.
<tr><td>18 <td>1<td>
<p style="margin-top:0">
File-format "write version". Currently, this field
is always set to 1. If a value greater than 1 is read by SQLite,
then the library will only open the file for read-only access.
<p style="margin-bottom:0">
This field and the next one are intended to be used for
forwards compatibility, should the need ever arise. If in the
future a version of SQLite is created that uses a file format
that may be safely read but not written by older versions of
SQLite, then this field will be set to a value greater than 1
to prevent older SQLite versions from writing to a file that
uses the new format.
<tr><td>19 <td>1<td>
<p style="margin-top:0">
File-format "read version". Currently, this
field is always set to 1. If a value greater than 1 is read
by SQLite, then the library will refuse to open the database
<p style="margin-bottom:0">
Like the "write version" described above, this field exists
to facilitate some degree of forwards compatibility, in case
it is ever required. If a version of SQLite created in the
future uses a file format that may not be safely read by older
SQLite versions, then this field will be set to a value greater
than 1.
<tr><td>20 <td>1<td>
Number of bytes of unused space at the end of each database
page. Usually this field is set to 0. If it is non-zero, then
it contains the number of bytes that are left unused at the
end of every database page (see section
<cite>pages_and_page_types</cite> for a description of a
database page).
<tr><td>21 <td>1<td>
Maximum fraction of an index tree page to use for
embedded content. This value is used to determine the maximum
size of a B-Tree cell to store as embedded content on a
page that is part of an index B-Tree. Refer to section
<cite>index_btree_cell_format</cite> for details.
<tr><td>22 <td>1<td>
Minimum fraction of an index B-Tree page to use for
embedded content when an entry uses one or more overflow pages.
This value is used to determine the portion of a B-Tree cell
that requires one or more overflow pages to store as embedded
content on a page that is part of an index B-Tree. Refer to
section <cite>index_btree_cell_format</cite> for details.
<tr><td>23 <td>1<td>
Minimum fraction of an table B-Tree leaf page to use for
embedded content when an entry uses one or more overflow pages.
This value is used to determine the portion of a B-Tree cell
that requires one or more overflow pages to store as embedded
content on a page that is a leaf of a table B-Tree. Refer to
section <cite>table_btree_cell_format</cite> for details.
<tr><td>24..27 <td>4<td>
<p style="margin-top:0">
The file change counter. Each time a database transaction is
committed, the value of the 32-bit unsigned integer stored in
this field is incremented.
<p style="margin-bottom:0">
SQLite uses this field to test the validity of its internal
cache. After unlocking the database file, SQLite may retain
a portion of the file cached in memory. However, since the file
is unlocked, another process may use SQLite to modify the
contents of the file, invalidating the internal cache of the
first process. When the file is relocked, the first process can
check if the value of the file change counter has been modified
since the file was unlocked. If it has not, then the internal
cache may be assumed to be valid and may be reused.
<tr><td>32..35 <td>4<td>
Page number of first freelist trunk page.
For more details, refer to section <cite>free_page_list</cite>.
<tr><td>36..39 <td>4<td>
Number of free pages in the database file.
For more details, refer to section <cite>free_page_list</cite>.
<tr><td>40..43 <td>4<td>
The schema version. Each time the database schema is modified (by
creating or deleting a database table, index, trigger or view)
the value of the 32-bit unsigned integer stored in this field
is incremented.
<tr><td>44..47 <td>4<td>
<p style="margin-top:0">
Schema layer file-format. This value is similar to the
"read-version" and "write-version" fields at offsets 18 and 19
of the database file header. If SQLite encounters a database
with a schema layer file-format value greater than the file-format
that it understands (currently 4), then SQLite will refuse to
access the database.
<p>
Usually, this value is set to 1. However, if any of the following
file-format features are used, then the schema layer file-format
must be set to the corresponding value or greater:
<ol start=2 style="margin-bottom:0">
<li> Implicit NULL values at the end of table records
(see section <cite>table_btree_content</cite>).
<li> Implicit default (non-NULL) values at the end of table
records (see section <cite>table_btree_content</cite>).
<li> Descending indexes (see section
<cite>index_btree_compare_func</cite>) and Boolean values
in database records (see section <cite>record_format</cite>,
serial types 8 and 9).
</ol>
<tr><td>48..51 <td>4<td>
Default pager cache size. This field is used by SQLite to store
the recommended pager cache size to use for the database.
<tr><td>52..55 <td>4<td>
For auto-vacuum capable databases, the numerically largest
root-page number in the database. Since page 1 is always the
root-page of the schema table (section <cite>schema_table</cite>),
this value is always non-zero for auto-vacuum databases. For
non-auto-vacuum databases, this value is always zero.
<tr><td>56..59 <td>4<td>
(constant) Database text encoding. A value of 1 means all
text values are stored using UTF-8 encoding. 2 indicates
little-endian UTF-16 text. A value of 3 means that the database
contains big-endian UTF-16 text.
<tr><td>60..63 <td>4<td>
The user-cookie value. A 32-bit integer value available to the
user for read/write access.
<tr><td>64..67 <td>4<td>
The incremental-vacuum flag. In non-auto-vacuum databases this
value is always zero. In auto-vacuum databases, this field is
set to 1 if "incremental vacuum" mode is enabled. If incremental
vacuum mode is not enabled, then the database file is reorganized
so that it contains no free pages (section
<cite>free_page_list</cite>) at the end of each database
transaction. If incremental vacuum mode is enabled, then the
reorganization is not performed until explicitly requested
by the user.
</table>
<p>
The four byte block beginning at offset 28 is unused. As is the
32 byte block beginning at offset 68.
</p>
<p>
Some of the following requirements state that certain database header
fields must contain defined constant values, even though the sqlite
database file format is designed to allow various values. This is
done to artificially constrain the definition of a
<i>well-formed database</i> in order to make implementation and
testing more practical.
<p class=req id=FF0030>
The first 16 bytes of a well-formed database file contain the UTF-8
encoding of the string "SQLite format 3" followed by a single
nul-terminator byte.
<p>
Following the 16 byte magic string in the file header is the
<i>page size</i>, a 2-byte field. See section
<cite>pages_and_page_types</cite> for details.
<p class=req id=FF0040>
The 19th byte (byte offset 18), the <i>file-format write version</i>,
of a well-formed database file contains the value 0x01.
<p class=req id=FF0050>
The 20th byte (byte offset 19), the <i>file-format read version</i>,
of a well-formed database file contains the value 0x01.
<p class=req id=FF0060>
The 21st byte (byte offset 20), the number of unused bytes on each
page, of a well-formed database file shall contain the value 0x00.
<p class=req id=FF0070>
The 22nd byte (byte offset 21), the maximum fraction of an index
B-Tree page to use for embedded content, of a well-formed database
file shall contain the value 0x40.
<p class=req id=FF0080>
The 23rd byte (byte offset 22), the minimum fraction of an index
B-Tree page to use for embedded content when using overflow pages,
of a well-formed database file contains the value 0x20.
<p class=req id=FF0090>
The 24th byte (byte offset 23), the minimum fraction of a table
B-Tree page to use for embedded content when using overflow pages,
of a well-formed database file contains the value 0x20.
<p class=req id=FF0100>
The 4 byte block starting at byte offset 24 of a well-formed
database file contains the <i>file change counter</i> formatted
as a 4-byte big-endian integer.
<p>
Following the <i>file change counter</i> in the database header are
two 4-byte fields related to the database file <i>free page list</i>.
See section <cite>free_page_list</cite> for details.
<p class=req id=FF0110>
The 4 byte block starting at byte offset 40 of a well-formed
database file contains the <i>schema version</i> formatted
as a 4-byte big-endian integer.
<p class=req id=FF0120>
The 4 byte block starting at byte offset 44 of a well-formed
database file, the <i>schema layer file format</i>, contains a
big-endian integer value between 1 and 4, inclusive.
<p class=req id=FF0130>
The 4 byte block starting at byte offset 48 of a well-formed
database file contains the <i>default pager cache size</i> formatted
as a 4-byte big-endian integer.
<p class=req id=FF0140>
The 4 byte block starting at byte offset 52 of a well-formed
database file contains the <i>auto-vacuum last root-page</i>
formatted as a 4-byte big-endian integer. If this value is non-zero,
the database is said to be an <i>auto-vacuum database</i>.
<p class=req id=FF0150>
The 4 byte block starting at byte offset 56 of a well-formed
database file, the <i>text encoding</i> contains a big-endian integer
value between 1 and 3, inclusive.
<p class=req id=FF0160>
The 4 byte block starting at byte offset 60 of a well-formed
database file contains the <i>user cookie</i> formatted
as a 4-byte big-endian integer.
<p class=req id=FF0170>
The 4 byte block starting at byte offset 64 of a well-formed
database file, the <i>incremental vaccum flag</i> contains a big-endian
integer value between 0 and 1, inclusive.
<p class=req id=FF0180>
In a well-formed non-autovacuum database (one with a zero stored
in the 4-byte big-endian integer value beginning at byte offset
52 of the database file header, the incremental vacuum flag is
set to 0.
<h3 id="pages_and_page_types">Pages and Page Types</h3>
<p>
The entire database file is divided into pages, each page consisting
of <i>page-size</i> bytes, where <i>page-size</i> is the 2-byte
integer value stored at offset 16 of the file header (see above).
The <i>page-size</i> is always a power of two between 512
(2<sup>9</sup>) and 32768 (2<sup>15</sup>). SQLite database files
always consist of an exact number of pages.
<p>
Pages are numbered beginning from 1, not 0. Page 1 consists of
the first <i>page-size</i> bytes of the database file. The file header
described in the previous section consumes the first 100 bytes of page
1.
<p>
Each page of the database file is one of the following:
<ul>
<li><b>A B-Tree page</b>. B-Tree pages are part of the tree
structures used to store database tables and indexes.
<li><b>An overflow page</b>. Overflow pages are used by particularly
large database records that do not fit on a single B-Tree page.
<li><b>A free page</b>. Free pages are pages within the database file
that are not being used to store meaningful data.
<li><b>A "pointer-map" page</b>. In auto-vacuum capable databases
(databases for which the 4 byte big-endian integer stored at
byte offset 52 of the file header is non-zero) some pages are
permanently designated "pointer-map" pages. See section
<cite>pointer_map_pages</cite> for details.
<li><b>The locking page</b>. The database page that starts at
byte offset 2<sup>30</sup>, if it is large enough to contain
such a page, is always left unused.
</ul>
<p class=req id=FF0190>
The <i>database page size</i> of a well-formed database, stored as a
2-byte big-endian unsigned integer at byte offset 16 of the file,
shall be an integer power of 2 between 512 and 32768, inclusive.
<p class=req id=FF0200>
The size of a <i>well formed database file</i> shall be an integer
multiple of the <i>database page size</i>.
<p class=req id=FF0210>
Each page of a <i>well formed database file</i> is exactly one of a
<i>B-Tree page</i>, an <i>overflow page</i>, a <i>free page</i>, a
<i>pointer-map page</i> or the <i>locking page</i>.
<p class=req id=FF0220>
The database page that starts at byte offset 2<sup>30</sup>, the
<i>locking page</i>, is never used for any purpose.
<h3 id=schema_table>The Schema Table</h3>
<p>
Apart from being the page that contains the file-header, page 1 of
the database file is special because it is the root page of the
B-Tree structure that contains the schema table data. From the SQL
level, the schema table is accessible via the name "sqlite_master".
<p>
The exact format of the B-Tree structure and the meaning of the term
"root page" is discussed in section <cite>btree_structures</cite>.
For now, it is sufficient to know that the B-Tree structure is a
data structure that stores a set of records. Each record is an
ordered set of SQL values (the format of which is described in
section <cite>record_format</cite>). Given the root page number of
the B-Tree structure (which is well known for the schema table), it
is possible to iterate through the set of records.
<p>
The schema table contains a record for each SQL table (including
virtual tables) except for sqlite_master, and for each index, trigger
and view in the logical database. There is also an entry for each
UNIQUE or PRIMARY KEY clause present in the definition of a database
table. Each record in the schema table contains exactly 5 values, in
the following order:
<table class=striped>
<tr><th>Field<th>Description
<tr><td>Schema item type.
<td>A string value. One of "table", "index", "trigger" or "view",
according to the schema item type. Entries associated with
UNIQUE or PRIMARY KEY clauses have this field set to "index".
<tr><td>Schema item name.
<td>A string value. The name of the database schema item (table,
index, trigger or view) associated with this record, if any.
Entries associated with UNIQUE or PRIMARY KEY clauses have
this field set to a string of the form
"sqlite_autoindex_<name>_<idx>" where <name>
is the name of the SQL table and <idx> is an integer
value.
<tr><td style="white-space:nowrap">Associated table name.
<td>A string value. For "table"
or "view" records this is a copy of the second (previous) value.
For "index" and "trigger" records, this field is set to the name
of the associated database table.
<tr><td style="white-space:nowrap">The "root page" number.
<td>For "trigger" and "view" records, as well as "table" records
associated with virtual tables, this is set to NULL. For other
"table" and "index" records (including those associated with
UNIQUE or PRIMARY KEY clauses), this field contains the root
page number (an integer) of the B-Tree structure that contains
the table or index data.
<tr><td>The SQL statement.
<td>A string value. The SQL statement used to create the schema
item (i.e. the complete text of an SQL "CREATE TABLE"
statement). This field contains an empty string for table
entries associated with PRIMARY KEY or UNIQUE clauses.
<span class=todo>Refer to some document that describes these
SQL statements more precisely.</span>
</table>
<p>
Logical database schema items other than non-virtual tables and indexes
(including indexes created by UNIQUE or PRIMARY key constraints) do not
require any other data structures to be created within the database
file.
<p>
Tables and indexes on the other hand, are represented within the
database file by both an entry in the schema table and a B-Tree
structure stored elsewhere in the file. The specific B-Tree associated
with each database table or index is identified by its root page
number, which is stored in the 4th field of the schema table record.
In a non-auto-vacuum database, the B-Tree root pages may be stored
anywhere within the database file. For an auto-vacuum database, all
B-Tree root pages must at all times form a contiguous set starting
at page 3 of the database file, skipping any pages that are required to
be used as pointer-map pages (see section
<cite>pointer_map_pages</cite>).
<p>
As noted in section <cite>file_header</cite>, in an auto-vacuum
database the page number of the page immediately following the
final root page in the contiguous set of root pages is stored
as a 4 byte big-endian integer at byte offset 52 of the database
file header. Unless that page is itself a pointer-map page, in which
case the page number of the page following it is stored instead.
<p>
For example, if the schema of a logical database is created using
the following SQL statements:
<pre>
CREATE TABLE abc(a, b, c);
CREATE INDEX i1 ON abc(b, c);
CREATE TABLE main.def(a PRIMARY KEY, b, c, UNIQUE(b, c));
CREATE VIEW v1 AS SELECT * FROM abc;
</pre>
<p>
Then the schema table would contain a total of 7 records, as follows:
<table class=striped>
<tr><th>Field 1<th>Field 2<th>Field 3<th>Field 4<th>Field 5
<tr><td>table <td>abc <td>abc <td>2 <td>CREATE TABLE abc(a, b, c)
<tr><td>index <td>i1 <td>abc <td>3 <td>CREATE INDEX i1 ON abc(b, c)
<tr><td>table <td>def <td>def <td>4 <td>CREATE TABLE def(a PRIMARY KEY, b, c, UNIQUE(b, c))
<tr><td>index <td>sqlite_autoindex_def_1 <td>def <td>5 <td>
<tr><td>index <td>sqlite_autoindex_def_2 <td>def <td>6 <td>
<tr><td>view <td>v1 <td>v1 <td>0 <td>CREATE VIEW v1 AS SELECT * FROM abc
</table>
<p class=req id=FF0230>
In a <i>well-formed database file</i>, the portion of the first
database page not consumed by the database file-header (all but the
first 100 bytes) contains the root node of a table B-Tree,
the <i>schema table</i>.
<p class=req id=FF0240>
All records stored in the <i>schema table</i> contain exactly five
fields.
<p>The following requirements describe "table" records.
<p class=req id=FF0250>
For each SQL table in the database apart from itself
("sqlite_master"), the <i>schema table</i> of a <i>well-formed
database file</i> contains an associated record.
<p class=req id=FF0260>
The first field of each <i>schema table</i> record associated with an
SQL table shall be the text value "table".
<p class=req id=FF0270>
The second field of each <i>schema table</i> record associated with an
SQL table shall be a text value set to the name of the SQL table.
<p class=req id=FF0280>
In a <i>well-formed database file</i>, the third field of all
<i>schema table</i> records associated with SQL tables shall contain
the same value as the second field.
<p class=req id=FF0290>
In a <i>well-formed database file</i>, the fourth field of all
<i>schema table</i> records associated with SQL tables that are not
virtual tables contains the page number (an integer value) of the root
page of the associated <i>table B-Tree</i> structure within the
database file.
<p class=req id=FF0300>
If the associated database table is a virtual table, the fourth
field of the <i>schema table</i> record shall contain an SQL NULL
value.
<p class=req id=FF0310>
In a well-formed database, the fifth field of all <i>schema table</i>
records associated with SQL tables shall contain a "CREATE TABLE"
or "CREATE VIRTUAL TABLE" statment (a text value). The details
of the statement shall be such that executing the statement
would create a table of precisely the same name and schema as the
existing database table.
<p>The following requirements describe "implicit index" records.
<p class=req id=FF0320>
For each PRIMARY KEY or UNIQUE constraint present in the definition
of each SQL table in the database, the schema table of a well-formed
database shall contain a record with the first field set to the text
value "index", and the second field set to a text value containing a
string of the form "sqlite_autoindex_<name>_<idx>", where
<name> is the name of the SQL table and <idx> is an
integer value.
<p class=req id=FF0330>
In a well-formed database, the third field of all schema table
records associated with SQL PRIMARY KEY or UNIQUE constraints shall
contain the name of the table to which the constraint applies (a
text value).
<p class=req id=FF0340>
In a well-formed database, the fourth field of all schema table
records associated with SQL PRIMARY KEY or UNIQUE constraints shall
contain the page number (an integer value) of the root page of the
associated index B-Tree structure.
<p class=req id=FF0350>
In a well-formed database, the fifth field of all schema table
records associated with SQL PRIMARY KEY or UNIQUE constraints shall
contain an SQL NULL value.
<p>The following requirements describe "explicit index" records.
<p class=req id=FF0360>
For each SQL index in the database, the schema table of a well-formed
database shall contain a record with the first field set to the text
value "index" and the second field set to a text value containing the
name of the SQL index.
<p class=req id=FF0370>
In a well-formed database, the third field of all schema table
records associated with SQL indexes shall contain the name of the
SQL table that the index applies to.
<p class=req id=FF0380>
In a well-formed database, the fourth field of all schema table
records associated with SQL indexes shall contain the page number
(an integer value) of the root page of the associated index B-Tree
structure.
<p class=req id=FF0390>
In a well-formed database, the fifth field of all schema table
records associated with SQL indexes shall contain an SQL "CREATE
INDEX" statement (a text value). The details of the statement shall
be such that executing the statement would create an index of
precisely the same name and content as the existing database index.
<p>The following requirements describe "view" records.
<p class=req id=FF0400>
For each SQL view in the database, the schema table of a well-formed
database shall contain a record with the first field set to the text
value "view" and the second field set to a text value containing the
name of the SQL view.
<p class=req id=FF0410>
In a well-formed database, the third field of all schema table
records associated with SQL views shall contain the same value as
the second field.
<p class=req id=FF0420>
In a well-formed database, the third field of all schema table
records associated with SQL views shall contain the integer value 0.
<p class=req id=FF0430>
In a well-formed database, the fifth field of all schema table
records associated with SQL indexes shall contain an SQL "CREATE
VIEW" statement (a text value). The details of the statement shall
be such that executing the statement would create a view of
precisely the same name and definition as the existing database view.
<p>The following requirements describe "trigger" records.
<p class=req id=FF0440>
For each SQL trigger in the database, the schema table of a well-formed
database shall contain a record with the first field set to the text
value "trigger" and the second field set to a text value containing the
name of the SQL trigger.
<p class=req id=FF0450>
In a well-formed database, the third field of all schema table
records associated with SQL triggers shall contain the name of the
database table or view to which the trigger applies.
<p class=req id=FF0460>
In a well-formed database, the third field of all schema table
records associated with SQL triggers shall contain the integer value 0.
<p class=req id=FF0470>
In a well-formed database, the fifth field of all schema table
records associated with SQL indexes shall contain an SQL "CREATE
TRIGGER" statement (a text value). The details of the statement shall
be such that executing the statement would create a trigger of
precisely the same name and definition as the existing database trigger.
<p>The following requirements describe the placement of B-Tree root
pages in auto-vacuum databases.
<p class=req id=FF0480>
In an auto-vacuum database, all pages that occur before the page
number stored in the <i>auto-vacuum last root-page</i> field
of the database file header (see FF0140) must be either B-Tree <i>root
pages</i>, <i>pointer-map pages</i> or the <i>locking page</i>.
<p class=req id=FF0490>
In an auto-vacuum database, no B-Tree <i>root pages</i> may occur
on or after the page number stored in the <i>auto-vacuum last root-page</i> field
of the database file header (see FF0140) must be either B-Tree <i>root
pages</i>, <i>pointer-map pages</i> or the <i>locking page</i>.
<h2 id="btree_structures">B-Tree Structures</h2>
<p>
A large part of any SQLite database file is given over to one or more
B-Tree structures. A single B-Tree structure is stored using one or more
database pages. Each page contains a single B-Tree node.
The pages used to store a single B-Tree structure need not form a
contiguous block. The page that contains the root node of a B-Tree
structure is known as the "root page".
<p>
SQLite uses two distinct variants of the B-Tree structure:
<ul>
<li>The <b>table B-Tree</b>, which uses 64-bit integer values for keys.
In a table B-Tree, an associated database record (section
<cite>record_format</cite>) is stored along with each entry. Table
B-Tree structures are described in detail in section
<cite>table_btrees</cite>.
<li>The <b>index B-Tree</b>, which uses database records as keys. Index
B-Tree structures are described in detail in section
<cite>index_btrees</cite>.
</ul>
<p class=req id=FF0500>
As well as the <i>schema table</i>, a <i>well-formed database file</i>
contains <i>N</i> table B-Tree structures, where <i>N</i> is the
number of non-virtual tables in the logical database, excluding the
sqlite_master table but including sqlite_sequence and other system
tables.
<p class=req id=FF0510>
A well-formed database file contains <i>N</i> table B-Tree structures,
where <i>N</i> is the number of indexes in the logical database,
including indexes created by UNIQUE or PRIMARY KEY clauses in the
declaration of SQL tables.
<h3 id="varint_format">Variable Length Integer Format</h3>
<p>
In several parts of the B-Tree structure, 64-bit twos-complement signed
integer values are stored in the "variable length integer format"
described here.
<p>
A variable length integer consumes from one to nine bytes of space,
depending on the value stored. Seven bits are used from each of
the first eight bytes present, and, if present, all eight from
the final ninth byte. Unless the full nine byte format is used, the
serialized form consists of all bytes up to and including the first
byte with the 0x80 bit cleared.
<p>
The number of bytes present depends on the position of the most
significant set bit in the 64-bit word. Negative numbers always have
the most significant bit of the word (the sign bit) set and so are
always encoded using the full nine bytes. Positive integers may be
encoded using less space. The following table shows the 9 different
length formats available for storing a variable length integer
value.
<table class=striped>
<tr><th>Bytes<th>Value Range<th>Bit Pattern
<tr><td>1<td>7 bit<td>0xxxxxxx
<tr><td>2<td>14 bit<td>1xxxxxxx 0xxxxxxx
<tr><td>3<td>21 bit<td>1xxxxxxx 1xxxxxxx 0xxxxxxx
<tr><td>4<td>28 bit<td>1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx
<tr><td>5<td>35 bit<td>1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx
<tr><td>6<td>42 bit<td>1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx
<tr><td>7<td>49 bit<td>1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx
<tr><td>8<td>56 bit<td>1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx
<tr><td>9<td>64 bit<td>1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx xxxxxxxx
</table>
<p>
When using the full 9 byte representation, the first byte contains
the 7 most significant bits of the 64-bit value. The final byte of
the 9 byte representation contains the 8 least significant bits of
the 64-bit value. When using one of the other representations, the
final byte contains the 7 least significant bits of the 64-bit value.
The second last byte, if present, contains the 7 next least signficant
bits of the value, and so on. The significant bits of the 64-bit
value for which no storage is provided are assumed to be zero.
<p>
When encoding a variable length integer, SQLite usually selects the
most compact representation that provides enough storage to accomadate
the most significant set bit of the value. This is not required
however, using more bytes than is strictly necessary when encoding
an integer is valid.
<table class=striped>
<tr><th>Decimal<th>Hexadecimal <th>Variable Length Integer
<tr><td>43 <td>0x000000000000002B <td>0x2B
<tr><td>200815 <td>0x000000000003106F <td>0x8C 0xA0 0x6F
<tr><td>-1 <td>0xFFFFFFFFFFFFFFFF
<td>0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF
<tr><td>-78056 <td>0xFFFFFFFFFFFECD56
<td>0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFD 0xCD 0x56
</table>
<p class=req id=FF0520>
A 64-bit signed integer value stored in <i>variable length integer</i>
format consumes from 1 to 9 bytes of space.
<p class=req id=FF0530>
The most significant bit of all bytes except the last in a serialized
<i>variable length integer</i> is always set. Unless the serialized
form consumes the maximum 9 bytes available, then the most significant
bit of the final byte of the representation is always cleared.
<p class=req id=FF0540>
The eight least significant bytes of the 64-bit twos-compliment
representation of a value stored in a 9 byte <i>variable length
integer</i> are stored in the final byte (byte offset 8) of the
serialized <i>variable length integer</i>. The other 56 bits are
stored in the 7 least significant bits of each of the first 8 bytes
of the serialized <i>variable length integer</i>, in order from
most significant to least significant.
<p class=req id=FF0550>
A <i>variable length integer</i> that consumes less than 9 bytes of
space contains a value represented as an <i>N</i>-bit unsigned
integer, where <i>N</i> is equal to the number of bytes consumed by
the serial representation (between 1 and 8) multiplied by 7. The
<i>N</i> bits are stored in the 7 least significant bits of each
byte of the serial representation, from most to least significant.
<h3 id="record_format">Database Record Format</h3>
<p>
A database record is a blob of data that represents an ordered
list of one or more SQL values. Database records are used in two
places in SQLite database files - as the associated data for entries
in table B-Tree structures, and as the key values in index B-Tree
structures. The size (number of bytes consumed by) a database record
depends on the values it contains.
<p>
Each database record consists of a short record header followed by
a data area. The record header consists of <i>N+1</i> variable
length integers (see section <cite>varint_format</cite>), where
<i>N</i> is the number of values stored in the record.
<p>
The first variable length integer in a record header contains the
size of the record header in bytes. The following <i>N</i> variable
length integer values each describe the type and size of the
records corresponding SQL value (the second integer in the record
header describes the first value in the record, etc.). Integer
values are interpreted according to the following table:
<table class=striped>
<tr><th>Header Value <th>Data type and size
<tr><td>0
<td>An SQL NULL value (type SQLITE_NULL). This value
consumes zero bytes of space in the record's data area.
<tr><td>1
<td>An SQL integer value (type SQLITE_INTEGER), stored as a
big-endian 1-byte signed integer.
<tr><td>2
<td>An SQL integer value (type SQLITE_INTEGER), stored as a
big-endian 2-byte signed integer.
<tr><td>3
<td>An SQL integer value (type SQLITE_INTEGER), stored as a
big-endian 3-byte signed integer.
<tr><td>4
<td>An SQL integer value (type SQLITE_INTEGER), stored as a
big-endian 4-byte signed integer.
<tr><td>5
<td>An SQL integer value (type SQLITE_INTEGER), stored as a
big-endian 6-byte signed integer.
<tr><td>6
<td>An SQL integer value (type SQLITE_INTEGER), stored as an
big-endian 8-byte signed integer.
<tr><td>7
<td>An SQL real value (type SQLITE_FLOAT), stored as an
8-byte IEEE floating point value.
<tr><td>8
<td>The literal SQL integer 0 (type SQLITE_INTEGER). The value
consumes zero bytes of space in the record's data area.
Values of this type are only present in databases with
a schema file format (the 32-bit integer at byte offset 44
of the database file header) value of 4 or greater.
<tr><td>9
<td>The literal SQL integer 1 (type SQLITE_INTEGER). The value
consumes zero bytes of space in the record's data area.
Values of this type are only present in databases with
a schema file format (the 32-bit integer at byte offset 44
of the database file header) value of 4 or greater.
<tr><td style="white-space:nowrap"><i>bytes</i> * 2 + 12
<td>Even values greater than 12 are used to signify a blob of
data (type SQLITE_BLOB) (<i>n</i>-12)/2 bytes in length, where
<i>n</i> is the integer value stored in the record header.
<tr><td style="white-space:nowrap"><i>bytes</i> * 2 + 13
<td>Odd values greater than 12 are used to signify a string
(type SQLITE_TEXT) (<i>n</i>-13)/2 bytes in length, where
<i>n</i> is the integer value stored in the record header.
</table>
<p>
Immediately following the record header is the data for each
of the record's values. A record containing <i>N</i> values is
depicted in figure <cite>figure_recordformat</cite>.
<center><img src="images/fileformat/recordformat.gif">
<p><i>Figure <span class=fig id=figure_recordformat></span> - Database Record Format.</i>
</center>
<p>
For each SQL value in the record, there is a blob of data stored
in the records data area. If the corresponding integer type value
in the record header is 0 (NULL), 8 (integer value 0) or 9 (integer
value 1), then the blob of data is zero bytes in length. Otherwise,
the length of the data field is as described in the table above.
<p>
The data field associated with a string value contains the string
encoded using the database encoding, as defined in the database
file header (see section <cite>file_header</cite>). No
nul-terminator character is stored in the database.
<p class=req id=FF0560>
A <i>database record</i> consists of a <i>database record header</i>,
followed by <i>database record data</i>. The first part of the
<i>database record header</i> is a <i>variable length integer</i>
containing the total size (including itself) of the header in bytes.
<p class=req id=FF0570>
Following the length field, the remainder of the <i>database record
header</i> is populated with <i>N</i> <i>variable length integer</i>
fields, where <i>N</i> is the number of database values stored in
the record.
<p class=req id=FF0580>
Following the <i>database record header</i>, the <i>database record
data</i> is made up of <i>N</i> variable length blobs of data, where
<i>N</i> is again the number of database values stored in the record.
The <i>n</i> blob contains the data for the <i>n</i>th value in
the database record. The size and format of each blob of data is
encoded in the corresponding <i>variable length integer</i> field
in the <i>database record header</i>.
<p class=req id=FF0590>
A value of 0 stored within the <i>database record header</i> indicates
that the corresponding database value is an SQL NULL. In this case
the blob of data in the data area is 0 bytes in size.
<p class=req id=FF0600>
A value of 1 stored within the <i>database record header</i> indicates
that the corresponding database value is an SQL integer. In this case
the blob of data contains the integer value, formatted as a 1-byte
big-endian signed integer.
<p class=req id=FF0610>
A value of 2 stored within the <i>database record header</i> indicates
that the corresponding database value is an SQL integer. In this case
the blob of data contains the integer value, formatted as a 2-byte
big-endian signed integer.
<p class=req id=FF0620>
A value of 3 stored within the <i>database record header</i> indicates
that the corresponding database value is an SQL integer. In this case
the blob of data contains the integer value, formatted as a 3-byte
big-endian signed integer.
<p class=req id=FF0630>
A value of 4 stored within the <i>database record header</i> indicates
that the corresponding database value is an SQL integer. In this case
the blob of data contains the integer value, formatted as a 4-byte
big-endian signed integer.
<p class=req id=FF0640>
A value of 5 stored within the <i>database record header</i> indicates
that the corresponding database value is an SQL integer. In this case
the blob of data contains the integer value, formatted as a 6-byte
big-endian signed integer.
<p class=req id=FF0650>
A value of 6 stored within the <i>database record header</i> indicates
that the corresponding database value is an SQL integer. In this case
the blob of data contains the integer value, formatted as a 8-byte
big-endian signed integer.
<p class=req id=FF0660>
A value of 7 stored within the <i>database record header</i> indicates
that the corresponding database value is an SQL real (floating
point number). In this case the blob of data contains an 8-byte
IEEE floating point number, stored in big-endian byte order.
<p class=req id=FF0670>
A value of 8 stored within the <i>database record header</i> indicates
that the corresponding database value is an SQL integer, value 0.
In this case the blob of data in the data area is 0 bytes in size.
<p class=req id=FF0680>
A value of 9 stored within the <i>database record header</i> indicates
that the corresponding database value is an SQL integer, value 1.
In this case the blob of data in the data area is 0 bytes in size.
<p class=req id=FF0690>
An even value greater than or equal to 12 stored within the
<i>database record header</i> indicates that the corresponding
database value is an SQL blob field. The blob of data contains the
value data. The blob of data is exactly (<i>n</i>-12)/2 bytes
in size, where <i>n</i> is the integer value stored in the
<i>database record header</i>.
<p class=req id=FF0700>
An odd value greater than or equal to 13 stored within the
<i>database record header</i> indicates that the corresponding
database value is an SQL text field. The blob of data contains the
value text stored using the <i>database encoding</i>, with no
nul-terminator. The blob of data is exactly (<i>n</i>-12)/2 bytes
in size, where <i>n</i> is the integer value stored in the
<i>database record header</i>.
<p>
The following database file properties define restrictions on the
integer values that may be stored within a
<i>database record header</i>.
<p class=req id=FF0710>
In a well-formed database file, if the values 8 or 9 appear within
any <i>database record header</i> within the database, then the
<i>schema-layer file format</i> (stored at byte offset 44 of the
database file header) must be set to 4.
<p class=req id=FF0720>
In a well-formed database file, the values 10 and 11, and all
negative values may not appear within any <i>database record header</i>
in the database.
<h3 id=index_btrees>Index B-Trees</h3>
<p>
As specified in section <cite>fileformat_overview</cite>, index
B-Tree structures store a unique set of the database records described
in the previous section. While in some cases, when there are very
few entries in the B-Tree, the entire structure may fit on a single
database page, usually the database records must be spread across
two or more pages. In this case, the pages are organized into a
tree structure with a single "root" page at the head of the tree.
<p>
Within the tree structure, each page is either an internal tree
node containing an ordered list of N references to child nodes
(page numbers) and N-1 database records, or a leaf node containing
M database records. The value of N may be different for each page, but
is always two or greater. Similarly, each leaf page may have a
different non-zero positive value for M. The tree is always of
uniform height, meaning the number of intermediate levels between
each leaf node page and the root page is the same.
<p>
Within both internal and leaf node pages, the records are stored in
sorted order. The comparison function used to determine the sort order
is described in section <cite>index_btree_compare_func</cite>.
<p>
Records are distributed throughout the tree such that for each
internal node, all records stored in the sub-tree headed by
the first child node ( C(0) ) are considered less than
the first record stored on the internal node ( R(0) ) by the
comparison function described in section
<cite>index_btree_compare_func</cite>. Similarly all records stored
in the sub-tree headed by C(n) are considered greater than R(n-1) but
less than R(n) for values of n between 1 and N-2, inclusive. All
records in the sub-tree headed by C(N-1) are greater than the
largest record stored on the internal node.
<center><img src="images/fileformat/indextree.gif">
<p><i>Figure <span class=fig id=figure_indextree></span> - Index B-Tree Tree Structure.</i>
</center>
<p>
Figure <cite>figure_indextree</cite> depicts one possible record
distribution for an index B-Tree containing records R1 to R26, assuming
that for all values of N, <i>R(N+1)>R(N)</i>. In total the B-Tree
structure uses 11 database file pages. Internal tree nodes contain
database records and references to child node pages. Leaf nodes contain
database records only.
<p class=req id=FF0730>
The pages in an index B-Tree structures are arranged into a tree
structure such that all leaf pages are at the same depth.
<p class=req id=FF0740>
Each leaf node page in an index B-Tree contains one or more
B-Tree cells, where each cell contains a database record.
<p class=req id=FF0750>
Each internal node page in an index B-Tree contains one or more
B-Tree cells, where each cell contains a child page number, <i>C</i>,
and a database record <i>R</i>. All database records stored within
the sub-tree headed by page <i>C</i> are smaller than record <i>R</i>,
according to the index sort order (see below). Additionally, unless
<i>R</i> is the smallest database record stored on the internal node
page, all integer keys within the sub-tree headed by <i>C</i> are
greater than <i>R<sub>-1</sub></i>, where <i>R<sub>-1</sub></i> is the
largest database record on the internal node page that is smaller
than <i>R</i>.
<p class=req id=FF0760>
As well as child page numbers associated with B-Tree cells, each
internal node page in an index B-Tree contains the page number
of an extra child page, the <i>right-child page</i>. All database
records stored in all B-Tree cells within the sub-tree headed by the
<i>right-child page</i> are greater than all database records
stored within B-Tree cells on the internal node page.
<p>
The precise way in which index B-Tree pages and cells are formatted is
described in subsequent sections.
<h4>Index B-Tree Content</h4>
<p>
The database file contains one index B-Tree for each database index
in the logical database, including those created by UNIQUE or
PRIMARY KEY clauses in table declarations. Each record stored in
an index B-Tree contains the same number of fields, the number of
indexed columns in the database index declaration plus one.
<p>
An index B-Tree contains an entry for each row in its associated
database table. The fields of the record used as the index B-Tree
key are copies of each of the indexed columns of the associated
database row, in order, followed by the rowid value of the same
row. See figure <cite>figure_examplepop</cite> for an example.
<p class=req id=FF0770>
In a well-formed database, each index B-Tree contains a single entry
for each row in the indexed logical database table.
<p class=req id=FF0780>
Each <i>database record</i> (key) stored by an index B-Tree in a
well-formed database contains the same number of values, the number
of indexed columns plus one.
<p class=req id=FF0790>
The final value in each <i>database record</i> (key) stored by an
index B-Tree in a well-formed database contains the rowid (an integer
value) of the corresponding logical database row.
<p class=req id=FF0800>
The first <i>N</i> values in each <i>database record</i> (key)
stored in an index B-Tree where <i>N</i> is the number of indexed
columns, contain the values of the indexed columns from the
corresponding logical database row, in the order specified for the
index.
<h4 id="index_btree_compare_func">Record Sort Order</h4>
<p>
This section defines the comparison function used when database
records are used as B-Tree keys for index B-Trees. The comparison
function is only defined when both database records contain the same
number of fields.
<p>
When comparing two database records, the first field of one
record is compared to the first field of the other. If they
are not equal, the next pair of fields are compared, and so
on. If all the fields in the database records are equal, then
the two records are considered equal. Otherwise, the result
of the comparison is determined by the first pair of inequal
fields.
<p>
Two database record fields (SQL values) are compared using the
following rules:
<ol>
<li>If both values are NULL, then they are considered equal.
<li>If one value is a NULL and the other is not, it is considered
the lesser of the two.
<li>If both values are either real or integer values, then the
comparison is done numerically.
<li>If one value is a real or integer value, and the other is
a text or blob value, then the numeric value is considered
lesser.
<li>If both values are text, then the collation function is used
to compare them. The collation function is a property of the
index column in which the values are found. <span class=todo>
Link to document with CREATE INDEX syntax.</span>
<li>If one value is text and the other a blob, the text value
is considered lesser.
<li>If both values are blobs, memcmp() is used to determine the
results of the comparison function. If one blob is a prefix
of the other, the shorter blob is considered lesser.
</ol>
<p>
Each column of a database index may be declared as "descending".
<span class=todo>Link to document with CREATE INDEX syntax.</span>
In SQLite database files with a schema layer file-format equal
to 4, this modifies the order in which the records are stored in
the corresponding index B-Tree structure. For each index column
declared as descending, the results of the above comparison
procedure are inverted.
<p>
The columns of database indexes created by UNIQUE or PRIMARY
KEY clauses are never treated as descending.
<p class=todo>
Need requirements style statements for this information. Easier
to do once collation sequences have been defined somewhere.
<h4 id=index_btree_page_format>Index B-Tree Page Format</h4>
<p>
Each index B-Tree page is divided into four sections that occur
in order on the page:
<ul>
<li> The 8 (leaf node pages) or 12 (internal tree node pages)
byte page-header.
<li> The cell offset array. This is a series of N big-endian 2-byte
integer values, where N is the number of records stored on
the page.
<li> A block of unused space. This may be 0 bytes in size.
<li> The cell content area consumes the remaining space on the page.
</ul>
<center><img src="images/fileformat/indexpage.gif">
<p><i>Figure <span class=fig id=figure_indexpage></span> - Index B-Tree Page Data.</i>
</center>
<p>
The 8 (leaf node pages) or 12 (internal tree node pages) byte page
header that begins each index B-Tree page is made up of a series of
1, 2 and 4 byte unsigned integer values as shown in the following
table. All values are stored in big-endian byte order.
<table class=striped>
<tr><th>Byte Range <th>Byte Size <th width=100%>Description
<tr><td>0 <td>1<td>B-Tree page flags. For an index B-Tree internal
tree node page, this is set to 0x02. For a
leaf node page, 0x0A.
<tr><td>1..2 <td>2<td>Byte offset of first block of free space on
this page. If there are no free blocks on this
page, this field is set to 0.
<tr><td>3..4 <td>2<td>Number of cells (entries) on this page.
<tr><td>5..6 <td>2<td>Byte offset of the first byte of the cell
content area (see figure
<cite>figure_indexpage</cite>), relative to the
start of the page.
<tr><td>7 <td>1<td>Number of fragmented free bytes on page.
<tr><td>8..11 <td>4<td>Page number of rightmost child-page (the
child-page that heads the sub-tree in which all
records are larger than all records stored on
this page). This field is not present for leaf
node pages.
</table>
<p>
The cell content area, which occurs last on the page, contains one
B-Tree cell for each record stored on the B-Tree page. On a leaf node
page, each cell is responsible for storing a database record only. On
an internal tree node page, each cell contains a database record and
the corresponding child page number ((R(0) and C(0)) are stored
together, for example - the cell record is considered greater than
all records stored in the sub-tree headed by the child page). The
final child page number is stored as part of the page header.
<p>
The B-Tree cells may be distributed throughout the cell content area
and may be interspersed with blocks of unused space. They are not
sorted within the cell content area in any particular order. The
serialized format of a B-Tree cell is described in detail in
section <cite>index_btree_cell_format</cite>.
<p>
The byte offset of each cell in the cell content area, relative
to the start of the page, is stored in the cell offset array. The
offsets are in sorted order according to the database records stored
in the corresponding cells. The first offset in the array is the
offset of the cell containing the smallest record on the page,
according to the comparison function defined in section
<cite>index_btree_compare_func</cite>.
<p>
As well as the block of unused space between the cell offset array and
the cell content area, which may be any size, there may be small blocks
of free space interspersed with the B-Tree cells within the cell
content area. These are classified into two classes, depending on their size:
<ul>
<li>Blocks of free-space consisting of 3 bytes or less are called
<b>fragments</b>. The total number of bytes consumed by all
fragments on a page is stored in the 1 byte unsigned integer at
byte offset 7 of the page header. The total number of fragmented
bytes on a single page is never greater than 255.
<li>Blocks of free-space consisting of more than 3 bytes of contiguous
space are called <b>free blocks</b>. All free blocks on a single
page are linked together into a singly linked list. The byte
offset (relative to the start of the page) of the first block in
the list is stored in the 2 byte unsigned integer stored at byte
offset 1 of the page header. The first two bytes of each free
block contain the byte offset (again relative to the start of
the page) of the next block in the list stored as a big-endian
unsigned integer. The first two bytes of the final block in the
list are set to zero. The third and fourth bytes of each free
block contain the total size of the free block in bytes, stored
as a 2 byte big-endian unsigned integer.
</ul>
<p class=req id=FF0810>
The <i>b-tree page flags</i> field (the first byte) of each database
page used as an internal node of an index B-Tree structure is set to
0x02.
<p class=req id=FF0820>
The <i>b-tree page flags</i> field (the first byte) of each database
page used as a leaf node of an index B-Tree structure is set to 0x0A.
<p>
The following requirements describe the <i>B-Tree page header</i>
present at the start of both index and table B-Tree pages.
<p class=req id=FF0830>
The first byte of each database page used as a B-Tree page contains
the <i>b-tree page flags</i> field. On page 1, the <i>b-tree page
flags</i> field is stored directly after the 100 byte file header
at byte offset 100.
<p class=req id=FF0840>
The number of B-Tree cells stored on a B-Tree page is stored as a
2-byte big-endian integer starting at byte offset 3 of the B-Tree
page. On page 1, this field is stored at byte offset 103.
<p class=req id=FF0850>
The 2-byte big-endian integer starting at byte offset 5 of each
B-Tree page contains the byte-offset from the start of the page
to the start of the <i>cell content area</i>, which consumes all space
from this offset to the end of the usable region of the page.
On page 1, this field is stored at byte offset 105. All B-Tree
cells on the page are stored within the cell-content area.
<p class=req id=FF0860>
On each page used as an internal node a of B-Tree structures, the
page number of the rightmost child node in the B-Tree structure is
stored as a 4-byte big-endian unsigned integer beginning at byte
offset 8 of the database page, or byte offset 108 on page 1.
<p>
This requirement describes the cell content offset array. It applies
to both B-Tree variants.
<p class=req id=FF0870>
Immediately following the <i>page header</i> on each B-Tree page is the
<i>cell offset array</i>, consisting of <i>N</i> 2-byte big-endian
unsigned integers, where <i>N</i> is the number of cells stored
on the B-Tree page (FF0840). On an internal node B-Tree page,
the cell offset array begins at byte offset 12, or on a leaf
page, byte offset 8. For the B-Tree node on page 1, these
offsets are 112 and 108, respectively.
<p class=req id=FF0880>
The <i>cell offset array</i> and the <i>cell content area</i> (FF0850)
may not overlap.
<p class=req id=FF0890>
Each value stored in the <i>cell offset array</i> must be greater
than or equal to the offset to the <i>cell content area</i> (FF0850),
and less than the database <i>page size</i>.
<p class=req id=FF0900>
The <i>N</i> values stored within the <i>cell offset array</i> are the
byte offsets from the start of the B-Tree page to the beginning of
each of the <i>N</i> cells stored on the page.
<p class=req id=FF0910>
No two B-Tree cells may overlap.
<p>
The following requirements govern management of free-space within the
page content area (both table and index B-Tree pages).
<p class=req id=FF0920>
Within the <i>cell content area</i>, all blocks of contiguous
free-space (space not used by B-Tree cells) greater than 3 bytes in
size are linked together into a linked list, the <i>free block list</i>.
Such blocks of free space are known as <i>free blocks</i>.
<p class=req id=FF0930>
The first two bytes of each <i>free block</i> contain the offset
of the next <i>free block</i> in the <i>free block list</i> formatted
as a 2-byte big-endian integer, relative to the start of the database
page. If there is no next <i>free block</i>, then the first two
bytes are set to 0x00.
<p class=req id=FF0940>
The second two bytes (byte offsets 2 and 3) of each <i>free block</i>
contain the total size of the <i>free block</i>, formatted as a 2-byte
big-endian integer.
<p class=req id=FF0950>
On all B-Tree pages, the offset of the first <i>free block</i> in the
<i>free block list</i>, relative to the start of the database page,
is stored as a 2-byte big-endian integer starting at byte offset
1 of the database page. If there is no first <i>free block</i>
(because the <i>free block list</i> is empty), then the two bytes
at offsets 1 and 2 of the database page are set to 0x00. On page 1,
this field is stored at byte offset 101 of the page.
<p class=req id=FF0960>
Within the cell-content area, all blocks of contiguous free-space
(space not used by B-Tree cells) less than or equal to 3 bytes in
size are known as <i>fragments</i>. The total size of all
<i>fragments</i> on a B-Tree page is stored as a 1-byte unsigned
integer at byte offset 7 of the database page. On page 1, this
field is stored at byte offset 107.
<h4 id=index_btree_cell_format>Index B-Tree Cell Format</h4>
<p>
For index B-Tree internal tree node pages, each B-Tree cell begins
with a child page-number, stored as a 4-byte big-endian unsigned
integer. This field is omitted for leaf pages, which have no
children.
<p>
Following the child page number is the total number of bytes
consumed by the cell's record, stored as a variable length integer
(see section <cite>varint_format</cite>).
<p>
If the record is small enough, it is stored verbatim in the cell.
A record is deemed to be small enough to be completely stored in
the cell if it consists of less than:
<pre>
<i>max-local</i> := <i>usable-size</i> * (<i>max-embedded-fraction</i> / 255 ) - 23
</pre>
<p>
bytes. In the formula above, <i>usable-size</i> is the page-size
in bytes less the number of unused bytes left at the end of every
page (as read from byte offset 20 of the file header), and
<i>max-embedded-fraction</i> is the value read from byte offset
21 of the file header.
<center><img src="images/fileformat/indexshortrecord.gif">
<p><i>Figure <span class=fig></span> - Small Record Index B-Tree Cell.</i>
</center>
<p>
If the cell record is larger than the maximum size identified by
the formula above, then only the first part of the record is stored
within the cell. The remainder is stored in an overflow-chain (see
section <cite>overflow_page_chains</cite> for details). Following
the part of the record stored within the cell is the page number
of the first page in the overflow chain, stored as a 4 byte
big-endian unsigned integer. The size of the part of the record
stored within the B-Tree cell (<i>local-size</i> in figure
<cite>figure_indexlongrecord</cite>) is calculated according to the
following algorithm:
<pre>
<i>min-local</i> := (<i>usable-size</i> - 12) * <i>min-embedded-fraction</i> / 255 - 23
<i>max-local</i> := (<i>usable-size</i> - 12) * <i>max-embedded-fraction</i> / 255 - 23
<i>local-size</i> := (<i>record-size</i> - <i>min-local</i>) % (<i>usable-size</i> - 4)
if( <i>local-size</i> > <i>max-local</i> )
<i>local-size</i> := <i>min-local</i>
</pre>
<p>
In the formula above, <i>usable-size</i> is the page-size
in bytes less the number of unused bytes left at the end of every
page (as read from byte offset 20 of the file header), and
<i>max-embedded-fraction</i> and <i>min-embedded-fraction</i> are
the values read from byte offsets 21 and 22 of the file header,
respectively.
<center><img src="images/fileformat/indexlongrecord.gif">
<p><i>Figure <span class=fig id=figure_indexlongrecord></span> -
Large Record Index B-Tree Cell.</i>
</center>
<p class=req id=FF0970>
Each B-Tree cell belonging to an internal node page of an index
B-Tree consists of a 4-byte big-endian unsigned integer, the
<i>child page number</i>, followed by a <i>variable length integer</i>
field, followed by a <i>database record</i>. The
<i>variable length integer</i> field contains the length of the
database record in bytes.
<p class=req id=FF0980>
Each B-Tree cell belonging to an leaf page of an index B-Tree
consists of a <i>variable length integer</i> field, followed by
a <i>database record</i>. The <i>variable length integer</i> field
contains the length of the database record in bytes.
<p class=req id=FF0990>
If the database record stored in an index B-Tree page is
sufficiently small, then the entire cell is stored within the
index B-Tree page. Sufficiently small is defined as equal to or
less than <i>max-local</i>, where:
<code>
<i>max-local</i> := (<i>usable-size</i> - 12) * 64 / 255 - 23</code>
<p class=req id=FF1000>
If the database record stored as part of an index B-Tree cell is too
large to be stored entirely within the B-Tree page (as defined by
FF0520), then only a prefix of the <i>database record</i> is stored
within the B-Tree page and the remainder stored in an <i>overflow
chain</i>. In this case, the database record prefix is immediately
followed by the page number of the first page of the
<i>overflow chain</i>, formatted as a 4-byte big-endian unsigned
integer.
<p class=req id=FF1010>
When a <i>database record</i> belonging to a table B-Tree cell is
stored partially within an <i>overflow page chain</i>, the size
of the prefix stored within the index B-Tree page is <i>N</i> bytes,
where <i>N</i> is calculated using the following algorithm:
<code>
<i>min-local</i> := (<i>usable-size</i> - 12) * 32 / 255 - 23
<i>max-local</i> := (<i>usable-size</i> - 12) * 64 / 255 - 23
<i>N</i> := <i>min-local</i> + ((<i>record-size</i> - <i>min-local</i>) % (<i>usable-size</i> - 4))
if( <i>N</i> > <i>max-local</i> ) <i>N</i> := <i>min-local</i></code>
<p>
Requirements FF1010 and FF0990 are similar to the algorithms
presented in the text above. However instead of
<i>min-embedded-fraction</i> and <i>max-embedded-fraction</i> the
requirements use the constant values 32 and 64, as well-formed
database files are required by FF0080 and FF0070 to store these
values in the relevant database file header fields.
<h3 id=table_btrees>Table B-Trees</h3>
<p>
As noted in section <cite>fileformat_overview</cite>, table B-Trees
store a set of unique 64-bit signed integer keys. Associated with
each key is a database record. As with index B-Trees, the database
file pages that make up a table B-Tree are organized into a tree
structure with a single "root" page at the head of the tree.
<p>
Unlike index B-Tree structures, where entries are stored on both
internal and leaf nodes, all entries in a table B-Tree are stored
in the leaf nodes. Within each leaf node, keys are stored in sorted
order.
<p>
Each internal tree node contains an ordered list of N references
to child pages, where N is some number greater than one. In a
similar manner to the way in which an index B-Tree page would
contain N-1 records, each internal table B-Tree node page also
contains a list of N-1 64-bit signed integer values in sorted order.
The keys are distributed throughout the tree such that for all internal
tree nodes, integer I(n) is equal to the largest key value stored in
the sub-tree headed by child page C(n) for values of n between 0 and
N-2, inclusive. Additionally, all keys stored in the sub-tree headed
by child page C(n+1) have values larger than that of I(n), for values
of n in the same range.
<center><img src="images/fileformat/tabletree.gif">
<p><i>Figure <span class=fig id=figure_tabletree></span> - Table B-Tree Tree Structure.</i>
</center>
<p>
Figure <cite>figure_tabletree</cite> depicts a table B-Tree containing
a contiguous set of 14 integer keys starting with 1. Each key <i>n</i>
has an associated database record R<i>n</i>. All the keys and their
associated records are stored in the leaf pages. The internal node
pages contain no database data, their only purpose is to provide
a way to navigate the tree structure.
<p class=req id=FF1020>
The pages in a table B-Tree structures are arranged into a tree
structure such that all leaf pages are at the same depth.
<p class=req id=FF1030>
Each leaf page in a table B-Tree structure contains one or more
B-Tree cells, where each cell contains a 64-bit signed integer key
value and a database record.
<p class=req id=FF1040>
Each internal node page in a table B-Tree structure contains one or
more B-Tree cells, where each cell contains a 64-bit signed integer
key value, <i>K</i>, and a child page number, <i>C</i>. All integer key
values in all B-Tree cells within the sub-tree headed by page <i>C</i>
are less than or equal to <i>K</i>. Additionally, unless <i>K</i>
is the smallest integer key value stored on the internal node page,
all integer keys within the sub-tree headed by <i>C</i> are greater
than <i>K<sub>-1</sub></i>, where <i>K<sub>-1</sub></i> is the largest
integer key on the internal node page that is smaller than <i>K</i>.
<p class=req id=FF1050>
As well as child page numbers associated with B-Tree cells, each
internal node page in a table B-Tree contains the page number
of an extra child page, the <i>right-child page</i>. All key values
in all B-Tree cells within the sub-tree headed by the <i>right-child
page</i> are greater than all key values stored within B-Tree cells
on the internal node page.
<p>
The precise way in which table B-Tree pages and cells are formatted is
described in subsequent sections.
<h4 id=table_btree_content>Table B-Tree Content</h4>
<p>
The database file contains one table B-Tree for each database table
in the logical database. Although some data may be duplicated in
index B-Tree structures, the table B-Tree is the primary location
of table data.
<p>
The table B-Tree contains exactly one entry for each row in the
database table. The integer key value used for the B-Tree entry is
the value of the "rowid" field of the corresponding logical row
in the database table. The database row fields are stored in the
record associated with the table B-Tree entry, in the same order
as they appear in the logical database table. The first field in
the record (see section <cite>record_format</cite>) contains the
value of the leftmost field in the database row, and so on.
<p>
If a database table column is declared as an INTEGER PRIMARY KEY,
then it is an alias for the rowid field, which is stored as the
table B-Tree key value. Instead of duplicating the integer value
in the associated record, the record field associated with the
INTEGER PRIMARY KEY column is always set to an SQL NULL.
<p>
Finally, if the schema layer file-format is greater than or equal
to 2, some of the records stored in table B-Trees may contain
less fields than the associated logical database table does columns.
If the schema layer file-format is exactly 2, then the logical
database table column values associated with the "missing" fields
are SQL NULL. If the schema layer file-format is greater than
2, then the values associated with the "missing" fields are
determined by the default value of the associated database table
columns.
<span class=todo>Reference to CREATE TABLE syntax. How are default
values determined?</span>
<p class=req id=FF1060>
In a well-formed database, each table B-Tree contains a single entry
for each row in the corresponding logical database table.
<p class=req id=FF1070>
The key value (a 64-bit signed integer) for each B-Tree entry is
the same as the value of the rowid field of the corresponding
logical database row.
<p class=req id=FF1080>
The SQL values serialized to make up each <i>database record</i>
stored as ancillary data in a table B-Tree shall be the equal to the
values taken by the <i>N</i> leftmost columns of the corresponding
logical database row, where <i>N</i> is the number of values in the
database record.
<p class=req id=FF1090>
If a logical database table column is declared as an "INTEGER
PRIMARY KEY", then instead of its integer value, an SQL NULL
shall be stored in its place in any database records used as
ancillary data in a table B-Tree.
<p>The following database properties discuss table B-Tree records
with implicit (default) values.
<p class=req id=FF1100>
If the database <i>schema layer file-format</i> (the value stored
as a 4-byte integer at byte offset 44 of the file header) is 1,
then all database records stored as ancillary data in a table
B-Tree structure have the same number of fields as there are
columns in the corresponding logical database table.
<p class=req id=FF1110>
If the database <i>schema layer file-format</i> value is two or
greater and the rightmost <i>M</i> columns of a row contain SQL NULL
values, then the corresponding record stored as ancillary data in
the table B-Tree has between <i>N</i>-<i>M</i> and <i>N</i> fields,
where <i>N</i> is the number of columns in the logical database
table.
<p class=req id=FF1120>
If the database <i>schema layer file-format</i> value is three or
greater and the rightmost <i>M</i> columns of a row contain their
default values according to the logical table declaration, then the
corresponding record stored as ancillary data in the table B-Tree
may have as few as <i>N</i>-<i>M</i> fields, where <i>N</i> is the
number of columns in the logical database table.
<h4>Table B-Tree Page Format</h4>
<p>
Table B-Tree structures use the same page format as index B-Tree
structures, described in section <cite>index_btree_page_format</cite>,
with the following differences:
<ul>
<li>The first byte of the page-header, the "flags" field, is set to
0x05 for internal tree node pages, and 0x0D for leaf pages.
<li>The content and format of the B-Tree cells is different. See
section <cite>table_btree_cell_format</cite> for details.
<li>The format of page 1 is the same as any other table B-Tree,
except that 100 bytes less than usual is available for content.
The first 100 bytes of page 1 is consumed by the database
file header.
</ul>
<p class=req id=FF1130>
In a <i>well-formed database file</i>, the first byte of each page used
as an internal node of a table B-Tree structure is set to 0x05.
<p class=req id=FF1140>
In a <i>well-formed database file</i>, the first byte of each page used
as a leaf node of a table B-Tree structure is set to 0x0D.
<p>
Most of the requirements specified in section
<cite>index_btree_page_format</cite> also apply to table B-Tree
pages. The wording of the requirements make it clear when this is
the case, either by refering to generic "B-Tree pages" or by
explicitly stating that the statement applies to both "table and
index B-Tree pages".
<h4 id=table_btree_cell_format>Table B-Tree Cell Format</h4>
<p>
Cells stored on internal table B-Tree nodes consist of exactly two
fields. The associated child page number, stored as a 4-byte
big-endian unsigned integer, followed by the 64-bit signed integer
value, stored as a variable length integer (section
<cite>varint_format</cite>). This is depicted graphically in figure
<cite>figure_tablenodecell</cite>.
<center><img src="images/fileformat/tablenodecell.gif">
<p><i>Figure <span class=fig id=figure_tablenodecell></span> - Table B-Tree Internal Node Cell.</i>
</center>
<p>
Cells of table B-Tree leaf pages are required to store a 64-bit
signed integer key and its associated database record. The first
two fields of all table B-Tree leaf page cells are the size of
the database record, stored as a <i>variable length integer</i>
(see section <cite>varint_format</cite>), followed by the key
value, also stored as a <i>variable length integer</i>. For
sufficiently small records, the entire record is stored in the
B-Tree cell following the record-size field. In this case,
sufficiently small is defined as less than or equal to:
<pre>
max-local := <i>usable-size</i> - 35
</pre>
<p>
bytes. Where <i>usable-size</i> is defined as the page-size
in bytes less the number of unused bytes left at the end of every
page (as read from byte offset 20 of the file header), and
<i>max-embedded-fraction</i> is the value read from byte offset
21 of the file header. This scenario, where the entire record is
stored within the B-Tree cell, is depicted in figure
<cite>figure_tableshortrecord</cite>.
<center><img src="images/fileformat/tableshortrecord.gif">
<p><i>Figure <span class=fig id=figure_tableshortrecord></span> - Table B-Tree Small Record Leaf Node Cell.</i>
</center>
<p>
If the record is too large to be stored entirely within the B-Tree
cell, then the first part of it is stored within the cell and the
remainder in an overflow chain (see section
<cite>overflow_page_chains</cite>). The size of the part of the
record stored within the B-Tree cell (<i>local-size</i> in figure
<cite>figure_tablelongrecord</cite>) is calculated according to
the following algorithm (a similar procedure to that used to
calculate the portion of an index B-Tree key to store within the cell
when an overflow chain is required):
<pre>
<i>min-local</i> := (<i>usable-size</i> - 12) * <i>min-embedded-fraction</i> / 255 - 23
<i>max-local</i> := <i>usable-size</i> - 35
<i>local-size</i> := <i>min-local</i> + (<i>record-size</i> - <i>min-local</i>) % (<i>usable-size</i> - 4)
if( <i>local-size</i> > <i>max-local</i> )
<i>local-size</i> := <i>min-local</i>
</pre>
<p>
In this case, <i>min-embedded-fraction</i> is the value read from
byte offset 22 of the file header. The layout of the cell in this
case, when an overflow-chain is required, is shown in figure
<cite>figure_tablelongrecord</cite>.
<center><img src="images/fileformat/tablelongrecord.gif">
<p><i>Figure <span class=fig id=figure_tablelongrecord></span> - Table B-Tree Large Record Leaf Node Cell.</i>
</center>
<p>
If the leaf page is page 1, then the value of <i>usable-size</i> is
as it would be for any other B-Tree page, even though the actual
usable size is 100 bytes less than this for page 1 (because the
first 100 bytes of the page is consumed by the database file
header).
<p>
The following requirements describe the format of table B-Tree
cells, and the distribution thereof between B-Tree and overflow
pages.
<p class=req id=FF1150>
B-Tree cells belonging to table B-Tree internal node pages consist
of exactly two fields, a 4-byte big-endian unsigned integer
immediately followed by a <i>variable length integer</i>. These
fields contain the child page number and key value respectively
(see FF1030).
<p class=req id=FF1160>
B-Tree cells belonging to table B-Tree leaf node pages consist
of three fields, two <i>variable length integer</i> values
followed by a database record. The size of the database record
in bytes is stored in the first of the two
<i>variable length integer</i> fields. The second of the two
<i>variable length integer</i> fields contains the 64-bit signed
integer key (see FF1030).
<p class=req id=FF1170>
If the size of the record stored in a table B-Tree leaf page cell
is less than or equal to (<i>usable page size</i>-35) bytes, then
the entire cell is stored on the B-Tree leaf page. In a well-formed
database, <i>usable page size</i> is the same as the database
<i>page size</i>.
<p class=req id=FF1180>
If a table B-Tree cell is too large to be stored entirely on
a leaf page (as defined by FF1170), then a prefix of the cell
is stored on the leaf page, and the remainder stored in an
<i>overflow page chain</i>. In this case the cell prefix
stored on the B-Tree leaf page is immediately followed by a
4-byte big-endian unsigned integer containing the page number
of the first overflow page in the chain.
<p class=req id=FF1190>
When a table B-Tree cell is stored partially in an
<i>overflow page chain</i>, the prefix stored on the B-Tree
leaf page consists of the two <i>variable length integer</i> fields,
followed by the first <i>N</i> bytes of the database record, where
<i>N</i> is determined by the following algorithm:
<code>
<i>min-local</i> := (<i>usable-size</i> - 12) * 255 / 32 - 23
<i>max-local</i> := (<i>usable-size</i> - 35)
<i>N</i> := <i>min-local</i> + (<i>record-size</i> - <i>min-local</i>) % (<i>usable-size</i> - 4)
if( <i>N</i> > <i>max-local</i> ) N := <i>min-local</i>
</code>
<p>
Requirement FF1190 is very similar to the algorithm presented in
the text above. Instead of <i>min-embedded-fraction</i>, it uses
the constant value 32, as well-formed database files are required
by FF0090 to store this value in the relevant database file
header field.
<h3 id="overflow_page_chains">Overflow Page Chains</h3>
<p>
Sometimes, a database record stored in either an index or table
B-Trees is too large to fit entirely within a B-Tree cell. In this
case part of the record is stored within the B-Tree cell and the
remainder stored on one or more overflow pages. The overflow pages
are chained together using a singly linked list. The first 4 bytes
of each overflow page is a big-endian unsigned integer value
containing the page number of the next page in the list. The
remaining usable database page space is available for record data.
<center><img src="images/fileformat/overflowpage.gif">
<p><i>Figure <span class=fig id=figure_overflowpage></span> - Overflow Page Format.</i>
</center>
<p>
The scenarios in which overflow pages are required and the number
of bytes stored within the B-Tree cell in each are described for
index and table B-Trees in sections
<cite>index_btree_cell_format</cite> and
<cite>table_btree_cell_format</cite> respectively. In each case
the B-Tree cell also stores the page number of the first page in
a linked list of overflow pages.
<p>
The amount of space available for record data on each overflow
page is:
<pre>
<i>available-space</i> := <i>usable-size</i> - 4
</pre>
<p>
Where <i>usable-size</i> is defined as the page-size in bytes less the
number of unused bytes left at the end of every page (as read from
byte offset 20 of the file header).
<p>
Each overflow page except for the last one in the linked list
contains <i>available-space</i> bytes of record data. The last
page in the list contains the remaining data, starting at byte
offset 4. The value of the "next page" field on the last page
in an overflow chain is undefined.
<p class=req id=FF1200>
A single <i>overflow page</i> may store up to <i>available-space</i>
bytes of database record data, where <i>available-space</i> is equal
to (<i>usable-size</i> - 4).
<p class=req id=FF1210>
When a database record is too large to store within a B-Tree page
(see FF1170 and FF1000), a prefix of the record is stored within
the B-Tree page and the remainder stored across <i>N</i> overflow
pages. In this case <i>N</i> is the minimum number of pages required
to store the portion of the record not stored on the B-Tree page,
given the maximum payload per overflow page defined by FF1200.
<p class=req id=FF1220>
The list of overflow pages used to store a single database record
are linked together in a singly linked list known as an
<i>overflow chain</i>. The first four bytes of each page except the
last in an <i>overflow chain</i> are used to store the page number
of the next page in the linked list, formatted as an unsigned
big-endian integer. The first four bytes of the last page in an
<i>overflow chain</i> are set to 0x00.
<p class=req id=FF1230>
Each overflow page except the last in an <i>overflow chain</i>
contains <i>N</i> bytes of record data starting at byte offset 4 of
the page, where <i>N</i> is the maximum payload per overflow page,
as defined by FF1200. The final page in an <i>overflow chain</i>
contains the remaining data, also starting at byte offset 4.
<h2 id=free_page_list>The Free Page List</h2>
<p>
Sometimes, after deleting data from the database, SQLite removes pages
from B-Tree structures. If these pages are not immediately required
for some other purpose, they are placed on the free page list. The
free page list contains those pages that are not currently being
used to store any valid data.
<p>
Each page in the free-list is classified as a free-list trunk page
or a free-list leaf page. All trunk pages are linked together into
a singly linked list (in the same way as pages in an overflow chain
are - see section <cite>overflow_page_chains</cite>). The first four
bytes of each trunk page contain the page number of the next trunk
page in the list, formatted as an unsigned big-endian integer. If
the trunk page is the last page in the linked list, the first four
bytes are set to zero.
<p>
Bytes 4 to 7 of each free-list trunk page contain the number of
references to free-list leaf pages (page numbers) stored on the
free-list trunk page. Each leaf page on the free-list is referenced
by exactly one trunk page.
<p>
The remaining space on a free-list trunk page is used to store the
page numbers of free-list leaf pages as 4 byte big-endian integers.
Each free-list trunk page contains up to:
<pre>
<i>max-leaf-pointers</i> := (<i>usable-size</i> - 8) / 4
</pre>
<p>
pointers, where <i>usable-size</i> is defined as the page-size in bytes
less the number of unused bytes left at the end of every page (as read
from byte offset 20 of the file header).
<center><img src="images/fileformat/freelistpage.gif">
<p><i>Figure <span class=fig id=figure_freelistpage></span> - Free List Trunk Page Format.</i>
</center>
<p>
All trunk pages in the free-list except for the first contain the
maximum possible number of references to leaf pages. <span class=todo>Is this actually true in an auto-vacuum capable database?</span> The page number
of the first page in the linked list of free-list trunk pages is
stored as a 4-byte big-endian unsigned integer at offset 32 of the
file header (section <cite>file_header</cite>).
<p class=req id=FF1240>
All <i>free pages</i> in a <i>well-formed database file</i> are part of
the database <i>free page list</i>.
<p class=req id=FF1250>
Each free page is either a <i>free list trunk</i> page or a
<i>free list leaf</i> page.
<p class=req id=FF1260>
All <i>free list trunk</i> pages are linked together into a singly
linked list. The first 4 bytes of each page in the linked list
contains the page number of the next page in the list, formatted
as an unsigned big-endian integer. The first 4 bytes of the last
page in the linked list are set to 0x00.
<p class=req id=FF1270>
The second 4 bytes of each <i>free list trunk</i> page contains
the number of </i>free list leaf</i> page numbers stored on the free list
trunk page, formatted as an unsigned big-endian integer.
<p class=req id=FF1280>
Beginning at byte offset 8 of each <i>free list trunk</i> page are
<i>N</i> page numbers, each formatted as a 4-byte unsigned big-endian
integers, where <i>N</i> is the value described in requirement FF1270.
<p class=req id=FF1290>
All page numbers stored on all <i>free list trunk</i> pages refer to
database pages that are <i>free list leaves</i>.
<p class=req id=FF1300>
The page number of each <i>free list leaf</i> page in a well-formed
database file appears exactly once within the set of pages numbers
stored on <i>free list trunk</i> pages.
<p>The following statements govern the two 4-byte big-endian integers
associated with the <i>free page list</i> structure in the database
file header.
<p class=req id=FF1310>
The total number of pages in the free list, including all <i>free list
trunk</i> and <i>free list leaf</i> pages, is stored as a 4-byte unsigned
big-endian integer at offset 36 of the database file header.
<p class=req id=FF1320>
The page number of the first page in the linked list of <i>free list
trunk</i> pages is stored as a 4-byte big-endian unsigned integer at
offset 32 of the database file header. If there are no <i>free list
trunk</i> pages in the database file, then the value stored at
offset 32 of the database file header is 0.
<h2 id=pointer_map_pages>Pointer Map Pages</h2>
<p>
Pointer map pages are only present in auto-vacuum capable databases.
A database is an auto-vacuum capable database if the value stored
at byte offset 52 of the file-header is non-zero.
<p>
If they are present, the pointer-map pages together form a lookup
table that can be used to determine the type and "parent page" of
any page in the database, given its page number. The lookup table
classifies pages into the following categories:
<table class=striped>
<tr><th>Page Type <th>Byte Value <th>Description
<tr><td style="white-space:nowrap">B-Tree Root Page<td>0x01
<td>The page is the root page of a table or index B-Tree structure.
There is no parent page number in this case, the value stored
in the pointer map lookup table is always zero.
<tr><td>Free Page<td>0x02
<td>The page is part of the free page list (section
<cite>free_page_list</cite>). There is no parent page in this
case, zero is stored in the lookup table instead of a parent
page number.
<tr><td>Overflow type 1<td>0x03
<td>The page is the first page in an overflow chain. The parent
page is the B-Tree page containing the B-Tree cell to which
the overflow chain belongs.
<tr><td style="white-space:nowrap">Overflow type 2<td>0x04
<td>The page is part of an overflow chain, but is not the first
page in that chain. The parent page is the previous page in
the overflow chain linked-list.
<tr><td>B-Tree Page<td>0x05
<td>The page is part of a table or index B-Tree structure, and is
not an overflow page or root page. The parent page is the page
containing the parent tree node in the B-Tree structure.
</table>
<p>
Pointer map pages themselves do not appear in the pointer-map lookup
table. Page 1 does not appear in the pointer-map lookup table either.
<center><img src="images/fileformat/pointermapentry.gif">
<p><i>Figure <span class=fig id=figure_pointermapentry></span> - Pointer Map Entry Format.</i>
</center>
<p>
Each pointer-map lookup table entry consumes 5 bytes of space.
The first byte of each entry indicates the page type, according to the
key described in the table above. The following 4 bytes store the
parent page number as a big-endian unsigned integer. This format is
depicted in figure <cite>figure_pointermapentry</cite>. Each
pointer-map page may therefore contain:
<pre>
<i>num-entries</i> := <i>usable-size</i> / 5
</pre>
<p>
entries, where <i>usable-size</i> is defined as the page-size in bytes
less the number of unused bytes left at the end of every page (as read
from byte offset 20 of the file header).
<p>
Assuming the database is auto-vacuum capable, page 2 is always a
pointer map page. It contains the pointer map lookup table entries for
pages 3 through (2 + <i>num-entries</i>), inclusive. The first 5 bytes
of page 2 contain the pointer map lookup table entry for page 3. Bytes
5 through 9, inclusive, contain the pointer map lookup table entry
for page 4, and so on.
<p>
The next pointer map page in the database is page number (3 +
<i>num-entries</i>), which contains the pointer map entries for pages
(4 + <i>num-entries</i>) through (3 + 2 * <i>num-entries</i>)
inclusive. In general, for any value of <i>n</i> greater than zero,
the following page is a pointer-map page that contains lookup
table entries for the <i>num-entries</i> pages that follow it in the
database file:
<pre>
<i>pointer-map-page-number</i> := 2 + <i>n</i> * <i>num-entries</i>
</pre>
<p class=req id=FF1330>
Non auto-vacuum databases do not contain pointer map pages.
<p class=req id=FF1340>
In an auto-vacuum database file, every <i>(num-entries + 1)</i>th
page beginning with page 2 is designated a pointer-map page, where
<i>num-entries</i> is calculated as:
<code>
<i>num-entries</i> := <i>database-usable-page-size</i> / 5
</code>
<p class=req id=FF1350>
In an auto-vacuum database file, each pointer-map page contains
a pointer map entry for each of the <i>num-entries</i> (defined by
FF1340) pages that follow it, if they exist.
<p class=req id=FF1360>
Each pointer-map page entry consists of a 1-byte page type and a
4-byte page parent number, 5 bytes in total.
<p class=req id=FF1370>
Pointer-map entries are packed into the pointer-map page in order,
starting at offset 0. The entry associated with the database
page that immediately follows the pointer-map page is located at
offset 0. The entry for the following page at offset 5 etc.
<p>
The following requirements govern the content of pointer-map entries.
<p class=req id=FF1380>
For each page except page 1 in an auto-vacuum database file that is
the root page of a B-Tree structure, the page type of the
corresponding pointer-map entry is set to the value 0x01 and the
parent page number is zero.
<p class=req id=FF1390>
For each page that is a part of an auto-vacuum database file free-list,
the page type of the corresponding pointer-map entry is set to the
value 0x02 and the parent page number is zero.
<p class=req id=FF1400>
For each page in a well-formed auto-vacuum database that is the first
page in an overflow chain, the page type of the corresponding
pointer-map entry is set to 0x03 and the parent page number field
is set to the page number of the B-Tree page that contains the start
of the B-Tree cell stored in the overflow-chain.
<p class=req id=FF1410>
For each page that is the second or a subsequent page in an overflow
chain, the page type of the corresponding pointer-map entry is set to
0x04 and the parent page number field is set to the page number of the
preceding page in the overflow chain.
<p class=req id=FF1420>
For each page that is not a root page but is a part of a B-Tree tree
structure (not part of an overflow chain), the page type of the
corresponding pointer-map entry is set to the value 0x05 and the parent
page number field is set to the page number of the parent node in the
B-Tree structure.
<h1 id="database_file_manipulation">Database File Manipulation</h1>
<p class=todo>
Better to do other higher level requirements before this.
<!--
<p>
The previous section described the format of a valid SQLite database
file. This section describes the way in which a database file is
transitioned between valid states by SQLite to effect various
operations, for example creating a table or inserting a database
record.
<p>
SQLite manipulates database files using combinations of the following
operations:
<ol>
<li>Database Initialization (see section
<cite>database_initialization</cite>).
<li>Modification of a global parameter stored in the database file
file-header (see section <cite>database_parameters</cite>).
<li>Creation of a new table.
<li>Creation of a new index.
<li>Creation of a new trigger or view.
<li>Destruction of a database table.
<li>Destruction of a database index.
<li>Destruction of a trigger or view.
<li>Insertion of an index entry.
<li>Removal of an index entry.
<li>Insertion of a table entry.
<li>Removal of a table entry.
</ol>
<p>
For example, execution of a single "UPDATE" statement may result in
many entries being removed and inserted into a table B-Tree and several
index B-Trees.
<p>
The list of operations above itemizes inserting and removing entries
from index and table B-Trees separately. Requirements specifying the
set of database file operations required by various SQL statements
may be found in [XXX]. The requirements in [XXX] are written so as to
ensure that the constraints relating the content of a table B-Tree and
its associated index B-Trees are met (see section YYY). By contrast the
requirements specifying the behaviour of the system when a
schema item (table, index, view or trigger) is added to or removed
from a database describe both the schema (sqlite_master) table
modifications and any additional modifications made to other parts
of the database file.
<p class=todo>
Fix this XXX reference. And add any other references to SQLiteRT
requirements documents that may specify requirements in terms of these
operations.
<p class=todo>
VACUUM? Auto-vacuum steps?
<h2 id=database_initialization>Database Creation/Initialization</h2>
<p>
As noted in section <cite>database_file_format</cite> a zero-length
file is a valid empty SQLite database. The first time such a
database is written to, SQLite initializes the the first page of
the database file as described by the following requirements, creating
a one-page empty SQLite database file.
<p class=req>
When initializing a new database file, SQLite shall set the
size of the file to <i>page-size</i> bytes, where <i>page-size</i>
is the database page size in bytes.
<p class=req>
When initializing a new database file, SQLite shall set the
first 16 bytes of the database file to the following values, from
first (byte offset 0) to last (byte offset 15): 0x53 0x51 0x4c
0x69 0x74 0x65 0x20 0x66 0x6f 0x72 0x6d 0x61 0x74 0x20 0x33 0x00.
<p>
The 16 byte values specified in the above requirement are the UTF-8
encoding of the string "SQLite file format 3" followed by a single
nul-terminator byte.
<p class=req>
When initializing a new database file, SQLite shall store the page
size in bytes as a 2-byte big-endian unsigned integer at byte
offset 16 of the new database file.
<p class=todo>
Some requirement to say where the initial page-size comes from. Probably
a reference to the SQL level requirements documenting the page-size
pragma.
<p class=todo>
Requirements for the other fields of the database header. Also to
describe how the part of page 1 after the header is initialized.
<h2 id=database_parameters>Setting Database Parameters</h2>
<p>
The database file-header contains three values that the system may
be required to update in response to the execution of SQL pragma
statements. These are:
<ul>
<li>The default pager-cache size,
<li>The user-cookie value,
<li>The incremental-vacuum flag.
</ul>
<p>
Requirements specified in <cite>sql_sqlitert_requirements</cite>
specify the various scenarios in which the system is required to set
one of the above three values. The following requirements explain
more specifically what the system has to do to achieve this.
<p class=req>
When required to set the default pager-cache size of a database, the
system shall store the new value as a 4-byte big-endian unsigned
integer starting at byte offset 48 of the database file.
<p class=req>
When required to set the user-cookie value of a database, the
system shall store the new value as a 4-byte big-endian unsigned
integer starting at byte offset 60 of the database file.
<p class=req>
When required to set the incremental vacuum flag of a database, the
system shall store the new value as a 4-byte big-endian unsigned
integer starting at byte offset 64 of the database file.
<h2>Creating and Deleting B-Tree Structures</h2>
<h3 id=btree_creation>Table/Index Creation</h3>
<p class=req>
When a new table or index is added to a non auto-vacuum database file,
the system shall initialize a newly allocated database page as the root
page of an empty table or index B-Tree, respectively.
<p class=todo>
Requirements describing in detail how an empty root page is initialized.
<p class=req>
When a new table is added to an auto-vacuum database file, the
system shall initialize the database page immediately following
the root page of the B-Tree structure with the numerically largest
root page number, skipping any pointer-map pages, as the root page of
an empty table B-Tree.
<p class=subreq>
When adding a new table or index to an auto-vacuum database file,
if the selected root page exists and is part of the database
free-list, the system shall remove it from the free-list.
<p class=subreq>
When adding a new table or index to an auto-vacuum database file,
if the selected root page exists and is not part of the database
free-list, then the system shall move the current contents of the
page to a newly allocated page. The system shall update all existing
references to the page within the database file to refer to the
new page number.
<p class=todo>
The above requirement needs to be tested for a B-Tree page, an
overflow page that is at the start of an overflow chain and an
overflow page that is not at the start of a chain. Maybe each
page type should have its own requirement.
<p class=subreq>
When adding a new table or index to an auto-vacuum database file,
the system shall update the pointer-map page entries corresponding
to both the new root page and, if the existing content of the page
was moved, the page to which the existing content was moved.
<p class=req>
When a new table is added to a database file, the system shall
add a new entry to the table B-Tree with page 1 as its root page (the
sqlite_master table).
<p class=todo>
Requirements for the contents of the new sqlite_master row.
<h3>Table/Index Destruction</h3>
<h2>Creating and Deleting Other Schema Items</h2>
<h2>Data Manipulation</h2>
<p>
This section describes the ways in which the system is required to
manipulate B-Tree structures within a database file. Various
operations at the SQL level require the system to insert or remove
entries from both table and index B-Trees. <span class=todo>It would be
good to reference some other requirements document here.</span>
<h3>Inserting Records</h3>
<h4>Table B-Tree Inserts</h4>
<p class=req>
When required to insert a new entry into a table B-Tree, the system
shall format a new table B-Tree leaf node cell containing the
integer key value and accompanying database record, and add the
new cell to a leaf node of the table B-Tree structure.
<p>
The format of a "table B-Tree leaf node cell", as specified in the
above requirement, is described in section
<cite>table_btree_cell_format</cite>.The following sub-requirements
state that the system shall "attempt to insert a cell" into a given
page. This operation may fail if there is not enough room on the
selected page.
<p class=subreq>
When inserting a a new table B-Tree leaf node cell, if the table
B-Tree is empty or consists of a single page only, the system shall
attempt to insert the new cell into the root page of the B-Tree.
<p class=subreq>
When inserting a a new table B-Tree leaf node cell, if the table
B-Tree constructor consists of more than one page, then the system
shall attempt to insert the new cell into the leaf node page that
currently contains the largest key value that is smaller than
the key value of the cell being inserted.
<p class=todo>
Finish this.
<h4>Index B-Tree Inserts</h4>
<p class=todo>
Finish this.
<h3>Removing Records</h3>
<p class=todo>
Finish this.
<h2>Page Management</h2>
<p>
When a new table or index is created, or when a new entry is added
to a table or index that does not fit into one of the B-Tree structures
existing pages, SQLite is required to select a new, presently unused,
database page to use for the new data. The new page may be obtained
using one of two methods:
<ul>
<li>The size of the database file may be extended by <i>page-size</i>
bytes, creating a new page at the end of the current database file.
<li>A database page that is currently part of the free page list
(refer to section <cite>free_page_list</cite>) may be removed from
the free-list and reused.
</ul>
<p>
This process of selecting a new page to use is refered to as
<i>allocating a new page</i>. See section <cite>page_allocation</cite>
for further details.
<p>
Similarly, when a table or index is removed from the database, or
when a B-Tree structure is reorganized such that it consumes fewer
pages, database pages may become unused. In this case the unused pages
must be added to the database free-list. This process is known as
<i>freeing a page</i>. See section <cite>page_deallocation</cite> for
details.
<p>
Sometimes, when operating on an auto-vacuum database, the system is
required to remove a specific page from the free page list. This
can occur:
<ul>
<li>When a new database table or index is created (section
<cite>btree_creation</cite>), or
<li>during an incremental-vacuum operation (section
<cite>incremental_vacuum</cite>).
</ul>
<p>
The requirements found in this section specify the manner in which
the system is required to manipulate the contents of database
free-list pages to achieve this are found in section
<cite>page_removal</cite>.
<h3 id=page_allocation>Page Allocation</h3>
<p>
If the database free-list is empty, then the new page is allocated
by extending the database file:
<p class=req>
When SQLite allocates a new database page, if the database free
page list is completely empty, the page shall be allocated by
extending the database file.
<p class=subreq>
If extending the database file by page-size bytes means that the
final page of the database file would be a pointer-map page, SQLite
shall extend the database file by (2 * page-size) bytes. The final
page of the database file after it has been extended shall be used
as the new (allocated) page.
<p class=subreq>
Otherwise, SQLite shall extend the database file by page-size bytes.
The final page of the database file after it has been extended shall
be used as the new (allocated) page.
<p>
In the above requirements, the condition "would be a pointer-map
page" is only true if both of the following are true:
<ul>
<li>The database the page belongs to is an auto-vacuum database, and
<li>The page number is equal to <i>(2 + n * (usable-size / 5))</i>
for some integer <i>n</i>.
</ul>
<p>
Otherwise, if the database free page list is not empty when SQLite
is required to allocate a new database page, then the page is
allocated by removing a page from the free-list for reuse.
<p class=req>
When SQLite allocates a new database page, if the database free page
list is not empty, then SQLite shall allocate the page by reusing
a page that is currently linked into the database free page list.
The page shall be removed from the free-list before it is resused.
<p class=subreq>
When allocating a page from the free-list, if the first page
in the free-list trunk has no leaves, then SQLite shall use this
page as the new (allocated) page. Otherwise, SQLite shall select
one of the leaves belonging to the first page in the free-list
trunk, remove its entry from the trunk page and use it as the
new (allocated) page.
<p class=todo>
How do we pick a single leaf from the set of leaves on the trunk
page?
<p class=subreq>
If the page removed from the free-list is the first page in the
free-list trunk, SQLite shall update the 4-byte integer value stored
at byte offset 32 to contain the page number of the second page
in the free-list trunk if it exists, or zero if the freelist is
now empty.
<p class=subreq>
After removing a page from the free-list, SQLite shall update
the 4-byte integer value stored at byte offset 36 of the database
file header to reflect the new number of pages in the database
free page list (one less than before).
<h3 id=page_deallocation>Page Deallocation</h3>
<p class=req>
If SQLite is required to free a database page when the free-list
is complete empty, or when the first page of the free-list trunk
is completely full, SQLite shall use the freed page as the new
head of the free-list trunk.
<p class=subreq>
When a newly freed page is made the head of the free-list trunk,
the system shall update the 4-byte integer value stored at byte
offset 32 to store the page number of the new free-list trunk head.
<p class=subreq>
When a newly freed page is made the new head of the free-list trunk,
the system shall store the page number of the previous head page
as a big-endian integer in the first 4 bytes of the page data, or
zero if the free-list was previously empty.
<p class=subreq>
When a newly freed page is made the new head of the free-list trunk,
the system shall set the second block of 4 bytes on the page to
zero (indicating that the free-list trunk page currently has no
leaves).
<p class=req>
If SQLite is required to free a database page when the first
page of the free-list trunk exists and has enough free space for
another leaf, the freed page shall become a leaf of the first
page in the free-list trunk.
<p class=req>
After removing a page from the free-list, SQLite shall update
the 4-byte integer value stored at byte offset 36 of the database
file header to reflect the new number of pages in the database
free page list (one less than before).
<h3 id=page_removal>Removing a Page From The Free List</h3>
<p class=req>
When the system is required to remove a specific page from the
database free-list, and that page is a free-list leaf page, the
system shall remove the specified leaf page number from the
relevant trunk page.
<p class=req>
When the system is required to remove a specific page from the
database free-list, and that page is an empty free-list trunk page,
the system shall remove the specified page from the free-list
trunk linked list.
<p class=req>
When the system is required to remove a specific page from the
database free-list, and that page is a non-empty free-list trunk
page, the system shall move the contents of the trunk page
to its first leaf page, remove the first leaf entry from the new
trunk page, then link the new trunk page into the free-list trunk
in place of the page being removed.
<h3 id=incremental_vacuum>Database Reorganization (auto-vacuum)</h3>
<p class=todo>
Requirements describing incremental vacuum steps. And on-commit
handling in auto-vacuum databases.
-->
<h1>References</h1>
<table id="refs" style="width:auto; margin: 1em 5ex">
<tr><td style="width:5ex" id="ref_comer_btree">[1]<td>
Douglas Comer, <u>Ubiquitous B-Tree</u>, ACM Computing Surveys (CSUR),
v.11 n.2, pages 121-137, June 1979.
<tr><td style="width:5ex" id="ref_knuth_btree">[2]<td>
Donald E. Knuth, <u>The Art Of Computer Programming, Volume 3:
"Sorting And Searching"</u>, pages 473-480. Addison-Wesley
Publishing Company, Reading, Massachusetts.
<tr><td style="width:5ex" id="capi_sqlitert_requirements">[3]<td>
C API Requirements Document.
<tr><td style="width:5ex" id="sql_sqlitert_requirements">[4]<td>
SQL Requirements Document.
<tr><td style="width:5ex" id="io_sqlitert_requirements">[5]<td>
File IO Requirements Document.
</table>
|