Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Change fileformat.in to use Tcl instead of javascript for toc generation etc.. |
|---|---|
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
0ca8a50964a39dc2cde2491bf7d50d65 |
| User & Date: | dan 2009-02-05 19:45:19 |
Context
|
2009-02-10
| ||
| 13:40 | Minor edits to the backup application note. Integrate the same into the other documents. check-in: d2614c5467 user: drh tags: trunk | |
|
2009-02-05
| ||
| 19:45 | Change fileformat.in to use Tcl instead of javascript for toc generation etc.. check-in: 0ca8a50964 user: dan tags: trunk | |
| 19:43 | Add a page with some backup API examples. check-in: 0c996cb98b user: dan 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 .. 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 ... 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 ... 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 ... 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 ... 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 ... 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 ... 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 ... 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 ... 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 ... 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 ... 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 ... 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 ... 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 .... 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 .... 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 .... 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 .... 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 .... 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 .... 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 .... 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 .... 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 .... 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 .... 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 .... 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 .... 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 .... 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 .... 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 .... 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 .... 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 .... 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 .... 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 .... 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 .... 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 .... 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 .... 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 .... 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 .... 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 .... 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 .... 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 |
<!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 --> <tcl> ############################################################################### # The actual text of requirments is stored in ../req/hlr30000.txt. During # the process in which this document is converted into HTML, TCL script runs # and imports requirements from that file over into this file whenever you # see: # <t*l>fileformat_import_requirement H00000</t*l> # unset -nocomplain ffreq hd_read_requirement_file $::DOC/req/hlr30000.txt ffreq proc fileformat_import_requirement {reqid} { hd_resolve [lindex $::ffreq($reqid) 1] } ############################################################################### </tcl> <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 ................................................................................ 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 ................................................................................ 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=H30010> <tcl>fileformat_import_requirement H30010</tcl> <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=H30020> <tcl>fileformat_import_requirement H30020</tcl> <!-- <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 ................................................................................ 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 ................................................................................ ...</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> ................................................................................ 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 ................................................................................ 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. ................................................................................ <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=H30030> <tcl>fileformat_import_requirement H30030</tcl> <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=H30040> <tcl>fileformat_import_requirement H30040</tcl> <p class=req id=H30050> <tcl>fileformat_import_requirement H30050</tcl> <p class=req id=H30060> <tcl>fileformat_import_requirement H30060</tcl> <p class=req id=H30070> <tcl>fileformat_import_requirement H30070</tcl> <p class=req id=H30080> <tcl>fileformat_import_requirement H30080</tcl> <p class=req id=H30090> <tcl>fileformat_import_requirement H30090</tcl> <p class=req id=H30100> <tcl>fileformat_import_requirement H30100</tcl> <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=H30110> <tcl>fileformat_import_requirement H30110</tcl> <p class=req id=H30120> <tcl>fileformat_import_requirement H30120</tcl> <p class=req id=H30130> <tcl>fileformat_import_requirement H30130</tcl> <p class=req id=H30140> <tcl>fileformat_import_requirement H30140</tcl> <p class=req id=H30150> <tcl>fileformat_import_requirement H30150</tcl> <p class=req id=H30160> <tcl>fileformat_import_requirement H30160</tcl> <p class=req id=H30170> <tcl>fileformat_import_requirement H30170</tcl> <p class=req id=H30180> <tcl>fileformat_import_requirement H30180</tcl> <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. ................................................................................ <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=H30190> <tcl>fileformat_import_requirement H30190</tcl> <p class=req id=H30200> <tcl>fileformat_import_requirement H30200</tcl> <p class=req id=H30210> <tcl>fileformat_import_requirement H30210</tcl> <p class=req id=H30220> <tcl>fileformat_import_requirement H30220</tcl> <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 ................................................................................ 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> ................................................................................ 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=H30230> <tcl>fileformat_import_requirement H30230</tcl> <p class=req id=H30240> <tcl>fileformat_import_requirement H30240</tcl> <p>The following requirements describe "table" records. <p class=req id=H30250> <tcl>fileformat_import_requirement H30250</tcl> <p class=req id=H30260> <tcl>fileformat_import_requirement H30260</tcl> <p class=req id=H30270> <tcl>fileformat_import_requirement H30270</tcl> <p class=req id=H30280> <tcl>fileformat_import_requirement H30280</tcl> <p class=req id=H30290> <tcl>fileformat_import_requirement H30290</tcl> <p class=req id=H30300> <tcl>fileformat_import_requirement H30300</tcl> <p class=req id=H30310> <tcl>fileformat_import_requirement H30310</tcl> <p>The following requirements describe "implicit index" records. <p class=req id=H30320> <tcl>fileformat_import_requirement H30320</tcl> <p class=req id=H30330> <tcl>fileformat_import_requirement H30330</tcl> <p class=req id=H30340> <tcl>fileformat_import_requirement H30340</tcl> <p class=req id=H30350> <tcl>fileformat_import_requirement H30350</tcl> <p>The following requirements describe "explicit index" records. <p class=req id=H30360> <tcl>fileformat_import_requirement H30360</tcl> <p class=req id=H30370> <tcl>fileformat_import_requirement H30370</tcl> <p class=req id=H30380> <tcl>fileformat_import_requirement H30380</tcl> <p class=req id=H30390> <tcl>fileformat_import_requirement H30390</tcl> <p>The following requirements describe "view" records. <p class=req id=H30400> <tcl>fileformat_import_requirement H30400</tcl> <p class=req id=H30410> <tcl>fileformat_import_requirement H30410</tcl> <p class=req id=H30420> <tcl>fileformat_import_requirement H30420</tcl> <p class=req id=H30430> <tcl>fileformat_import_requirement H30430</tcl> <p>The following requirements describe "trigger" records. <p class=req id=H30440> <tcl>fileformat_import_requirement H30440</tcl> <p class=req id=H30450> <tcl>fileformat_import_requirement H30450</tcl> <p class=req id=H30460> <tcl>fileformat_import_requirement H30460</tcl> <p class=req id=H30470> <tcl>fileformat_import_requirement H30470</tcl> <p>The following requirements describe the placement of B-Tree root pages in auto-vacuum databases. <p class=req id=H30480> <tcl>fileformat_import_requirement H30480</tcl> <p class=req id=H30490> <tcl>fileformat_import_requirement H30490</tcl> <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". ................................................................................ <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=H30500> <tcl>fileformat_import_requirement H30500</tcl> <p class=req id=H30510> <tcl>fileformat_import_requirement H30510</tcl> <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 ................................................................................ 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. ................................................................................ <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=H30520> <tcl>fileformat_import_requirement H30520</tcl> <p class=req id=H30530> <tcl>fileformat_import_requirement H30530</tcl> <p class=req id=H30540> <tcl>fileformat_import_requirement H30540</tcl> <p class=req id=H30550> <tcl>fileformat_import_requirement H30550</tcl> <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> 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=H30560> <tcl>fileformat_import_requirement H30560</tcl> <p class=req id=H30570> <tcl>fileformat_import_requirement H30570</tcl> <p class=req id=H30580> <tcl>fileformat_import_requirement H30580</tcl> <p class=req id=H30590> <tcl>fileformat_import_requirement H30590</tcl> <p class=req id=H30600> <tcl>fileformat_import_requirement H30600</tcl> <p class=req id=H30610> <tcl>fileformat_import_requirement H30610</tcl> <p class=req id=H30620> <tcl>fileformat_import_requirement H30620</tcl> <p class=req id=H30630> <tcl>fileformat_import_requirement H30630</tcl> <p class=req id=H30640> <tcl>fileformat_import_requirement H30640</tcl> <p class=req id=H30650> <tcl>fileformat_import_requirement H30650</tcl> <p class=req id=H30660> <tcl>fileformat_import_requirement H30660</tcl> <p class=req id=H30670> <tcl>fileformat_import_requirement H30670</tcl> <p class=req id=H30680> <tcl>fileformat_import_requirement H30680</tcl> <p class=req id=H30690> <tcl>fileformat_import_requirement H30690</tcl> <p class=req id=H30700> <tcl>fileformat_import_requirement H30700</tcl> <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=H30710> <tcl>fileformat_import_requirement H30710</tcl> <p class=req id=H30720> <tcl>fileformat_import_requirement H30720</tcl> <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 ................................................................................ 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=H30730> <tcl>fileformat_import_requirement H30730</tcl> <p class=req id=H30740> <tcl>fileformat_import_requirement H30740</tcl> <p class=req id=H30750> <tcl>fileformat_import_requirement H30750</tcl> <p class=req id=H30760> <tcl>fileformat_import_requirement H30760</tcl> <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=H30770> <tcl>fileformat_import_requirement H30770</tcl> <p class=req id=H30780> <tcl>fileformat_import_requirement H30780</tcl> <p class=req id=H30790> <tcl>fileformat_import_requirement H30790</tcl> <p class=req id=H30800> <tcl>fileformat_import_requirement H30800</tcl> <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 ................................................................................ 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 ................................................................................ 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=H30810> <tcl>fileformat_import_requirement H30810</tcl> <p class=req id=H30820> <tcl>fileformat_import_requirement H30820</tcl> <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=H30830> <tcl>fileformat_import_requirement H30830</tcl> <p class=req id=H30840> <tcl>fileformat_import_requirement H30840</tcl> <p class=req id=H30850> <tcl>fileformat_import_requirement H30850</tcl> <p class=req id=H30860> <tcl>fileformat_import_requirement H30860</tcl> <p> This requirement describes the cell content offset array. It applies to both B-Tree variants. <p class=req id=H30870> <tcl>fileformat_import_requirement H30870</tcl> <p class=req id=H30880> <tcl>fileformat_import_requirement H30880</tcl> <p class=req id=H30890> <tcl>fileformat_import_requirement H30890</tcl> <p class=req id=H30900> <tcl>fileformat_import_requirement H30900</tcl> <p class=req id=H30910> <tcl>fileformat_import_requirement H30910</tcl> <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=H30920> <tcl>fileformat_import_requirement H30920</tcl> <p class=req id=H30930> <tcl>fileformat_import_requirement H30930</tcl> <p class=req id=H30940> <tcl>fileformat_import_requirement H30940</tcl> <p class=req id=H30950> <tcl>fileformat_import_requirement H30950</tcl> <p class=req id=H30960> <tcl>fileformat_import_requirement H30960</tcl> <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 ................................................................................ </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 ................................................................................ <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=H30970> <tcl>fileformat_import_requirement H30970</tcl> <p class=req id=H30980> <tcl>fileformat_import_requirement H30980</tcl> <p class=req id=H30990> <tcl>fileformat_import_requirement H30990</tcl> <p class=req id=H31000> <tcl>fileformat_import_requirement H31000</tcl> <p class=req id=H31010> <tcl>fileformat_import_requirement H31010</tcl> <p> Requirements H31010 and H30990 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 H30080 and H30070 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> ................................................................................ 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=H31020> <tcl>fileformat_import_requirement H31020</tcl> <p class=req id=H31030> <tcl>fileformat_import_requirement H31030</tcl> <p class=req id=H31040> <tcl>fileformat_import_requirement H31040</tcl> <p class=req id=H31050> <tcl>fileformat_import_requirement H31050</tcl> <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 ................................................................................ 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=H31060> <tcl>fileformat_import_requirement H31060</tcl> <p class=req id=H31070> <tcl>fileformat_import_requirement H31070</tcl> <p class=req id=H31080> <tcl>fileformat_import_requirement H31080</tcl> <p class=req id=H31090> <tcl>fileformat_import_requirement H31090</tcl> <p>The following database properties discuss table B-Tree records with implicit (default) values. <p class=req id=H31100> <tcl>fileformat_import_requirement H31100</tcl> <p class=req id=H31110> <tcl>fileformat_import_requirement H31110</tcl> <p class=req id=H31120> <tcl>fileformat_import_requirement H31120</tcl> <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 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=H31130> <tcl>fileformat_import_requirement H31130</tcl> <p class=req id=H31140> <tcl>fileformat_import_requirement H31140</tcl> <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 ................................................................................ <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). 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 ................................................................................ </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=H31150> <tcl>fileformat_import_requirement H31150</tcl> <p class=req id=H31160> <tcl>fileformat_import_requirement H31160</tcl> <p class=req id=H31170> <tcl>fileformat_import_requirement H31170</tcl> <p class=req id=H31180> <tcl>fileformat_import_requirement H31180</tcl> <p class=req id=H31190> <tcl>fileformat_import_requirement H31190</tcl> <p> Requirement H31190 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 H30090 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 ................................................................................ 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=H31200> <tcl>fileformat_import_requirement H31200</tcl> <p class=req id=H31210> <tcl>fileformat_import_requirement H31210</tcl> <p class=req id=H31220> <tcl>fileformat_import_requirement H31220</tcl> <p class=req id=H31230> <tcl>fileformat_import_requirement H31230</tcl> <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> ................................................................................ <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=H31240> <tcl>fileformat_import_requirement H31240</tcl> <p class=req id=H31250> <tcl>fileformat_import_requirement H31250</tcl> <p class=req id=H31260> <tcl>fileformat_import_requirement H31260</tcl> <p class=req id=H31270> <tcl>fileformat_import_requirement H31270</tcl> <p class=req id=H31280> <tcl>fileformat_import_requirement H31280</tcl> <p class=req id=H31290> <tcl>fileformat_import_requirement H31290</tcl> <p class=req id=H31300> <tcl>fileformat_import_requirement H31300</tcl> <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=H31310> <tcl>fileformat_import_requirement H31310</tcl> <p class=req id=H31320> <tcl>fileformat_import_requirement H31320</tcl> <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: ................................................................................ database file: <pre> <i>pointer-map-page-number</i> := 2 + <i>n</i> * <i>num-entries</i> </pre> <p class=req id=H31330> <tcl>fileformat_import_requirement H31330</tcl> <p class=req id=H31340> <tcl>fileformat_import_requirement H31340</tcl> <p class=req id=H31350> <tcl>fileformat_import_requirement H31350</tcl> <p class=req id=H31360> <tcl>fileformat_import_requirement H31360</tcl> <p class=req id=H31370> <tcl>fileformat_import_requirement H31370</tcl> <p> The following requirements govern the content of pointer-map entries. <p class=req id=H31380> <tcl>fileformat_import_requirement H31380</tcl> <p class=req id=H31390> <tcl>fileformat_import_requirement H31390</tcl> <p class=req id=H31400> <tcl>fileformat_import_requirement H31400</tcl> <p class=req id=H31410> <tcl>fileformat_import_requirement H31410</tcl> <p class=req id=H31420> <tcl>fileformat_import_requirement H31420</tcl> <h1 id=journal_file_format>Journal File Format</h1> <p> This section describes the format used by an SQLite <i>journal file</i>. <p> A journal file consists of one or more <i>journal headers</i>, zero or more <i>journal records</i> and optionally a <i>master journal ................................................................................ second set of zero or more <i>journal records</i> and so on. There is no limit to the number of <i>journal headers</i> a journal file may contain. Following the <i>journal headers</i> and their accompanying sets of <i>journal records</i> may be the optional <i>master journal pointer</i>. Or, the file may simply end following the final <i>journal record</i>. <h2 id=journal_header_format>Journal Header Format</h2> <p> A <i>journal header</i> is <i>sector-size</i> bytes in size, where <i> sector-size</i> is the value returned by the xSectorSize method of the file handle opened on the database file. Only the first 28 bytes of the <i>journal header</i> are used, the remainder may contain garbage data. The first 28 bytes of each <i>journal header</i> consists of an eight byte block set to a well-known value, followed by five big-endian 32-bit unsigned integer fields. <center><img src="images/fileformat/journal_header.gif"> <p><i>Figure <span class=fig id=figure_journal_header></span> - Journal Header Format</i> </center> <p> Figure <cite>figure_journal_header</cite> graphically depicts the layout of a <i>journal header</i>. The individual fields are described in the following table. The offsets in the 'byte offset' column of the table are relative to the start of the <i>journal header</i>. <table class=striped> <tr><th>Byte offset<th>Size in bytes<th width=100%>Description <tr><td>0<td>8<td>The <b>journal magic</b> field always contains a well-known 8-byte string value used to identify SQLite journal files. The well-known sequence of byte values is: <pre>0xd9 0xd5 0x05 0xf9 0x20 0xa1 0x63 0xd7</pre> <tr><td>8<td>4<td>This field, the <b>record count</b>, is set to the number of <i>journal records</i> that follow this <i>journal header</i> in the <i>journal file</i>. <tr><td>12<td>4<td>The <b>checksum initializer</b> field is set to a pseudo-random value. It is used as part of the algorithm to calculate the checksum for all <i>journal records</i> that follow this <i>journal header</i>. <tr><td>16<td>4<td>This field, the <b>database page count</b>, is set to the number of pages that the <i>database file</i> contained before any modifications associated with <i>write transaction</i> are applied. <tr><td>20<td>4<td>This field, the <b>sector size</b>, is set to the <i>sector size</i> of the device on which the <i>journal file</i> was created, in bytes. This value is required when reading the journal file to determine the size of each <i>journal header</i>. <tr><td>24<td>4<td>The <b>page size</b> field contains the database page size used by the corresponding <i>database file</i> when the <i>journal file</i> was created, in bytes. </table> <p> All <i>journal headers</i> are positioned in the file so that they start at a <i>sector size</i> aligned offset. To achieve this, unused space may be left between the start of the second and subsequent <i>journal headers</i> and the end of the <i>journal records</i> associated with the previous header. <h2 id=journal_record_format>Journal Record Format</h2> <p> Each <i>journal record</i> contains the original data for a database page modified by the <i>write transaction</i>. If a rollback is required, then this data may be used to restore the contents of the database page to the state it was in before the <i>write transaction</i> was started. <center><img src="images/fileformat/journal_record.gif"> <p><i>Figure <span class=fig id=figure_journal_record></span> - Journal Record Format</i> </center> <p> A <i>journal record</i>, depicted graphically by figure <cite>figure_journal_record</cite>, contains three fields, as described in the following table. Byte offsets are relative to the start of the <i>journal record</i>. <table class=striped> <tr><th>Byte offset<th>Size in bytes<th width=100%>Description <tr><td>0<td>4<td>The page number of the database page associated with this <i>journal record</i>, stored as a 4 byte big-endian unsigned integer. <tr><td>4<td><i>page-size<td> This field contains the original data for the page, exactly as it appeared in the database file before the <i>write transaction</i> began. <tr><td style="white-space: nowrap">4 + <i>page-size</i><td>4<td> This field contains a checksum value, calculated based on the contents of the journaled database page data (the previous field) and the values stored in the <i>checksum initializer</i> field of the preceding <i>journal header</i>. </table> <p> The set of <i>journal records</i> that follow a <i>journal header</i> in a <i>journal file</i> are packed tightly together. There are no alignment requirements for <i>journal records</i> as there are for <i>journal headers</i>. <h2>Master Journal Pointer</h2> <p> To support <i>atomic</i> transactions that modify more than one database file, SQLite sometimes includes a <i>master journal pointer</i> record in a <i>journal file</i>. A <i>master journal pointer</i> contains the name of a <i>master journal-file</i> along with a check-sum and some well-known values that allow the ................................................................................ journal pointer</i> is always positioned at a <i>sector size</i> aligned offset. If the <i>journal record</i> or <i>journal header</i> that appears immediately before the <i>master journal pointer</i> does not end at an aligned offset, then unused space is left between the end of the <i>journal record</i> or <i>journal header</i> and the start of the <i>master journal pointer</i>. <center><img src="images/fileformat/master_journal_ptr.gif"> <p><i>Figure <span class=fig id=figure_master_journal_ptr></span> - Master Journal Pointer Format</i> </center> <p> A <i>master journal pointer</i>, depicted graphically by figure <cite>figure_master_journal_ptr</cite>, contains five fields, as described in the following table. Byte offsets are relative to the start of the <i>master journal pointer</i>. <table class=striped> <tr><th>Byte offset<th>Size in bytes<th width=100%>Description <tr><td>0<td>4<td>This field, the <b>locking page number</b>, is always set to the page number of the database <i>locking page</i> stored as a 4-byte big-endian integer. The <i>locking page</i> is the page that begins at byte offset 2<super>30</super> of the database file. Even if the database file is large enough to contain the <i>locking page</i>, the <i>locking page</i> is never used to store any data and so the first four bytes of of a valid <i>journal record</i> will never contain this value. <tr><td>4<td><i>name-length</i><td> The <b>master journal name</b> field contains the name of the master journal file, encoded as a utf-8 string. There is no nul-terminator appended to the string. <tr><td>4 + <i>name-length</i><td><i>4<td> The <b>name-length</b> field contains the length of the previous field in bytes, formatted as a 4-byte big-endian unsigned integer. <tr><td>8 + <i>name-length</i><td><i>4<td> The <b>checksum</b> field contains a checksum value stored as a 4-byte big-endian signed integer. The checksum value is calculated as the sum of the bytes that make up the <i> master journal name</i> field, interpreting each byte as an 8-bit signed integer. <tr><td style="white-space: nowrap">12 + <i>name-length</i><td><i>8<td> Finally, the <b>journal magic</b> field always contains a well-known 8-byte string value; the same value stored in the first 8 bytes of a <i>journal header</i>. The well-known sequence of bytes is: <pre>0xd9 0xd5 0x05 0xf9 0x20 0xa1 0x63 0xd7</pre> </table> <!-- <h1 id="database_file_traversal">Database File Structure Traversal</h1> <h2>B-Tree Cursors</h2> <h2>B-Tree Access Strategies</h2> <h3>Full Linear Scan</h3> <h3>Seek to Value</h3> <h3>Range Scan</h3> <h2>Retrieving Record Values</h2> <h1 id="database_file_manipulation">Database File Manipulation</h1> <h2>Creating a Database</h2> <h2>Table B-Trees</h2> <h3>Creating a new Table B-Tree</h3> <h3>Deleting a Table B-Tree</h3> <h3>Adding an Entry to a Table B-Tree</h3> ................................................................................ <h2>Overflow Chains</h2> <h2>Allocating/Deallocating Pages</h2> <h2>Allocating a Page</h2> <h2>Deallocating a Page</h2> <h2>Auto-Vacuum Commit Operations</h2> --> <!-- <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> ................................................................................ <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. ................................................................................ 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, ................................................................................ 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. ................................................................................ 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> ................................................................................ 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. ................................................................................ </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 ................................................................................ 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, ................................................................................ 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 ................................................................................ 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> |
< < < < < < < < | < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | | | | | | | | | < > | < | | | | | | | | | | | | | | | | | | | | | > | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | < > | < | | | | | | | | | | | | | | | | | | < > | < > | | | | | | | | | | | | < < | | | | | | | | | | | | | | | | | | | | | | | | | < | < < < | < | | | | | | < > | < > | | | | | | | | | | | | | | | | | < < < | < < | < | | | | | | < > | < > | | | | | < > | < | | | | | | | | | | | | | | | | | | < < | | | | | | | | | | | | | < < | | | | | | | | | | < < | | | | | | | < < | | | | | | | | | | < < | | | | | | | | | | | | | | | > > > > > > > > > |
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 ... 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 ... 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 ... 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 ... 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 ... 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 ... 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 ... 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 ... 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 ... 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 ... 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 ... 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 .... 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 .... 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 .... 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 .... 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 .... 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 .... 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 .... 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 .... 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 .... 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 .... 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 .... 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 .... 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 .... 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 .... 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 .... 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 .... 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 .... 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 .... 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 .... 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 .... 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 .... 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 .... 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 .... 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 .... 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 .... 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 .... 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 .... 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 .... 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 |
<!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">
</head>
<body>
<div id=document_title>SQLite Database File Format</div>
<div id=toc_header>Table Of Contents</div>
<tcl>
###############################################################################
# The actual text of requirments is stored in ../req/hlr30000.txt. During
# the process in which this document is converted into HTML, TCL script runs
# and imports requirements from that file over into this file whenever you
# see:
# <t*l>fileformat_import_requirement H00000</t*l>
#
unset -nocomplain ffreq
hd_read_requirement_file $::DOC/req/hlr30000.txt ffreq
proc fileformat_import_requirement {reqid} {
return [lindex $::ffreq($reqid) 1]
}
###############################################################################
catch { array unset ::SectionNumbers }
set ::SectionNumbers(1) 0
set ::SectionNumbers(2) 0
set ::SectionNumbers(3) 0
set ::SectionNumbers(fig) 0
catch { set TOC "" }
catch { array unset ::References }
proc H {iLevel zTitle {zName ""}} {
set zNumber ""
for {set i 1} {$i <= 4} {incr i} {
if {$i < $iLevel} {
append zNumber "$::SectionNumbers($i)."
}
if {$i == $iLevel} {
append zNumber "[incr ::SectionNumbers($i)]."
}
if {$i > $iLevel} {
set ::SectionNumbers($i) 0
}
}
set zNumber [string range $zNumber 0 end-1]
if {$zName == ""} {
set zName [string range "section_[string map {. _} $zNumber]" 0 end-1]
} else {
set ::References($zName) [list $zNumber $zTitle]
}
append ::TOC [subst {
<div style="margin-left:[expr $iLevel*6]ex">
<a href="#$zName">${zNumber}. $zTitle</a>
</a></div>
}]
return "<h$iLevel id=\"$zName\">$zNumber $zTitle</h$iLevel>\n"
}
proc h1 {args} {uplevel H 1 $args}
proc h2 {args} {uplevel H 2 $args}
proc h3 {args} {uplevel H 3 $args}
proc h4 {args} {uplevel H 4 $args}
proc Figure {zImage zName zCaption} {
incr ::SectionNumbers(fig)
set ::References($zName) [list $::SectionNumbers(fig) $zCaption]
subst {
<center>
<a name="$zName"></a>
<img src="images/fileformat/$zImage">
<p><i>Figure $::SectionNumbers(fig) - $zCaption</i>
</center>
}
}
proc FixReferences {body} {
foreach {key value} [array get ::References] {
foreach {zNumber zTitle} $value {}
lappend l <cite>$key</cite> "<cite><a href=\"#$key\" title=\"$zTitle\">$zNumber</a></cite>"
}
string map $l $body
}
proc Table {} {
set ::Stripe 1
return "<table class=striped>"
}
proc Tr {} {
set ::Stripe [expr {($::Stripe+1)%2}]
if {$::Stripe} {
return "<tr style=\"background-color:#DDDDDD\">"
} else {
return "<tr>"
}
}
set body [subst -novariables {
[h1 "Document Overview"]
[h2 "Scope and Purpose"]
<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
................................................................................
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"]
<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"]
<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
................................................................................
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 "SQLite Database Files" sqlite_database_files]
<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=H30010>
[fileformat_import_requirement H30010]
<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=H30020>
[fileformat_import_requirement H30020]
<!--
<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 "Database File Format Details" database_file_format]
<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
................................................................................
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 "File Format Overview" "fileformat_overview"]
<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
................................................................................
...</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>.
[Figure examplepop.gif figure_examplepop "Example B-Tree Data"]
[h2 "Global Structure"]
<p>
The following sections and sub-sections describe precisely the format
used to house the B-Tree structures within an SQLite database file.
[h3 "File Header" "file_header"]
<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>
................................................................................
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]
[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
................................................................................
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.
................................................................................
<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=H30030>
[fileformat_import_requirement H30030]
<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=H30040>
[fileformat_import_requirement H30040]
<p class=req id=H30050>
[fileformat_import_requirement H30050]
<p class=req id=H30060>
[fileformat_import_requirement H30060]
<p class=req id=H30070>
[fileformat_import_requirement H30070]
<p class=req id=H30080>
[fileformat_import_requirement H30080]
<p class=req id=H30090>
[fileformat_import_requirement H30090]
<p class=req id=H30100>
[fileformat_import_requirement H30100]
<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=H30110>
[fileformat_import_requirement H30110]
<p class=req id=H30120>
[fileformat_import_requirement H30120]
<p class=req id=H30130>
[fileformat_import_requirement H30130]
<p class=req id=H30140>
[fileformat_import_requirement H30140]
<p class=req id=H30150>
[fileformat_import_requirement H30150]
<p class=req id=H30160>
[fileformat_import_requirement H30160]
<p class=req id=H30170>
[fileformat_import_requirement H30170]
<p class=req id=H30180>
[fileformat_import_requirement H30180]
[h3 "Pages and Page Types" "pages_and_page_types"]
<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.
................................................................................
<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=H30190>
[fileformat_import_requirement H30190]
<p class=req id=H30200>
[fileformat_import_requirement H30200]
<p class=req id=H30210>
[fileformat_import_requirement H30210]
<p class=req id=H30220>
[fileformat_import_requirement H30220]
[h3 "The Schema Table" schema_table]
<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
................................................................................
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]
[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>
................................................................................
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]
[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=H30230>
[fileformat_import_requirement H30230]
<p class=req id=H30240>
[fileformat_import_requirement H30240]
<p>The following requirements describe "table" records.
<p class=req id=H30250>
[fileformat_import_requirement H30250]
<p class=req id=H30260>
[fileformat_import_requirement H30260]
<p class=req id=H30270>
[fileformat_import_requirement H30270]
<p class=req id=H30280>
[fileformat_import_requirement H30280]
<p class=req id=H30290>
[fileformat_import_requirement H30290]
<p class=req id=H30300>
[fileformat_import_requirement H30300]
<p class=req id=H30310>
[fileformat_import_requirement H30310]
<p>The following requirements describe "implicit index" records.
<p class=req id=H30320>
[fileformat_import_requirement H30320]
<p class=req id=H30330>
[fileformat_import_requirement H30330]
<p class=req id=H30340>
[fileformat_import_requirement H30340]
<p class=req id=H30350>
[fileformat_import_requirement H30350]
<p>The following requirements describe "explicit index" records.
<p class=req id=H30360>
[fileformat_import_requirement H30360]
<p class=req id=H30370>
[fileformat_import_requirement H30370]
<p class=req id=H30380>
[fileformat_import_requirement H30380]
<p class=req id=H30390>
[fileformat_import_requirement H30390]
<p>The following requirements describe "view" records.
<p class=req id=H30400>
[fileformat_import_requirement H30400]
<p class=req id=H30410>
[fileformat_import_requirement H30410]
<p class=req id=H30420>
[fileformat_import_requirement H30420]
<p class=req id=H30430>
[fileformat_import_requirement H30430]
<p>The following requirements describe "trigger" records.
<p class=req id=H30440>
[fileformat_import_requirement H30440]
<p class=req id=H30450>
[fileformat_import_requirement H30450]
<p class=req id=H30460>
[fileformat_import_requirement H30460]
<p class=req id=H30470>
[fileformat_import_requirement H30470]
<p>The following requirements describe the placement of B-Tree root
pages in auto-vacuum databases.
<p class=req id=H30480>
[fileformat_import_requirement H30480]
<p class=req id=H30490>
[fileformat_import_requirement H30490]
[h2 "B-Tree Structures" "btree_structures"]
<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".
................................................................................
<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=H30500>
[fileformat_import_requirement H30500]
<p class=req id=H30510>
[fileformat_import_requirement H30510]
[h3 "Variable Length Integer Format" "varint_format"]
<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
................................................................................
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]
[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.
................................................................................
<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]
[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=H30520>
[fileformat_import_requirement H30520]
<p class=req id=H30530>
[fileformat_import_requirement H30530]
<p class=req id=H30540>
[fileformat_import_requirement H30540]
<p class=req id=H30550>
[fileformat_import_requirement H30550]
[h3 "Database Record Format" "record_format"]
<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>
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]
[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>.
[Figure recordformat.gif figure_recordformat "Database Record Format"]
<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=H30560>
[fileformat_import_requirement H30560]
<p class=req id=H30570>
[fileformat_import_requirement H30570]
<p class=req id=H30580>
[fileformat_import_requirement H30580]
<p class=req id=H30590>
[fileformat_import_requirement H30590]
<p class=req id=H30600>
[fileformat_import_requirement H30600]
<p class=req id=H30610>
[fileformat_import_requirement H30610]
<p class=req id=H30620>
[fileformat_import_requirement H30620]
<p class=req id=H30630>
[fileformat_import_requirement H30630]
<p class=req id=H30640>
[fileformat_import_requirement H30640]
<p class=req id=H30650>
[fileformat_import_requirement H30650]
<p class=req id=H30660>
[fileformat_import_requirement H30660]
<p class=req id=H30670>
[fileformat_import_requirement H30670]
<p class=req id=H30680>
[fileformat_import_requirement H30680]
<p class=req id=H30690>
[fileformat_import_requirement H30690]
<p class=req id=H30700>
[fileformat_import_requirement H30700]
<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=H30710>
[fileformat_import_requirement H30710]
<p class=req id=H30720>
[fileformat_import_requirement H30720]
[h3 "Index B-Trees" index_btrees]
<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
................................................................................
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.
[Figure indextree.gif figure_indextree "Index B-Tree Tree Structure"]
<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=H30730>
[fileformat_import_requirement H30730]
<p class=req id=H30740>
[fileformat_import_requirement H30740]
<p class=req id=H30750>
[fileformat_import_requirement H30750]
<p class=req id=H30760>
[fileformat_import_requirement H30760]
<p>
The precise way in which index B-Tree pages and cells are formatted is
described in subsequent sections.
[h4 "Index B-Tree Content"]
<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=H30770>
[fileformat_import_requirement H30770]
<p class=req id=H30780>
[fileformat_import_requirement H30780]
<p class=req id=H30790>
[fileformat_import_requirement H30790]
<p class=req id=H30800>
[fileformat_import_requirement H30800]
[h4 "Record Sort Order" "index_btree_compare_func"]
<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
................................................................................
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 "Index B-Tree Page Format" index_btree_page_format]
<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>
[Figure indexpage.gif figure_indexpage "Index B-Tree Page Data"]
<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]
[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
................................................................................
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=H30810>
[fileformat_import_requirement H30810]
<p class=req id=H30820>
[fileformat_import_requirement H30820]
<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=H30830>
[fileformat_import_requirement H30830]
<p class=req id=H30840>
[fileformat_import_requirement H30840]
<p class=req id=H30850>
[fileformat_import_requirement H30850]
<p class=req id=H30860>
[fileformat_import_requirement H30860]
<p>
This requirement describes the cell content offset array. It applies
to both B-Tree variants.
<p class=req id=H30870>
[fileformat_import_requirement H30870]
<p class=req id=H30880>
[fileformat_import_requirement H30880]
<p class=req id=H30890>
[fileformat_import_requirement H30890]
<p class=req id=H30900>
[fileformat_import_requirement H30900]
<p class=req id=H30910>
[fileformat_import_requirement H30910]
<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=H30920>
[fileformat_import_requirement H30920]
<p class=req id=H30930>
[fileformat_import_requirement H30930]
<p class=req id=H30940>
[fileformat_import_requirement H30940]
<p class=req id=H30950>
[fileformat_import_requirement H30950]
<p class=req id=H30960>
[fileformat_import_requirement H30960]
[h4 "Index B-Tree Cell Format" index_btree_cell_format]
<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
................................................................................
</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.
[Figure indexshortrecord.gif figure_indexshortrecord "Small Record Index B-Tree Cell"]
<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
................................................................................
<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.
[Figure indexlongrecord.gif figure_indexlongrecord "Large Record Index B-Tree Cell"]
<p class=req id=H30970>
[fileformat_import_requirement H30970]
<p class=req id=H30980>
[fileformat_import_requirement H30980]
<p class=req id=H30990>
[fileformat_import_requirement H30990]
<p class=req id=H31000>
[fileformat_import_requirement H31000]
<p class=req id=H31010>
[fileformat_import_requirement H31010]
<p>
Requirements H31010 and H30990 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 H30080 and H30070 to store these
values in the relevant database file header fields.
[h3 "Table B-Trees" table_btrees]
<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>
................................................................................
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.
[Figure tabletree.gif figure_tabletree "Table B-Tree Tree Structure"]
<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=H31020>
[fileformat_import_requirement H31020]
<p class=req id=H31030>
[fileformat_import_requirement H31030]
<p class=req id=H31040>
[fileformat_import_requirement H31040]
<p class=req id=H31050>
[fileformat_import_requirement H31050]
<p>
The precise way in which table B-Tree pages and cells are formatted is
described in subsequent sections.
[h4 "Table B-Tree Content" table_btree_content]
<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
................................................................................
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=H31060>
[fileformat_import_requirement H31060]
<p class=req id=H31070>
[fileformat_import_requirement H31070]
<p class=req id=H31080>
[fileformat_import_requirement H31080]
<p class=req id=H31090>
[fileformat_import_requirement H31090]
<p>The following database properties discuss table B-Tree records
with implicit (default) values.
<p class=req id=H31100>
[fileformat_import_requirement H31100]
<p class=req id=H31110>
[fileformat_import_requirement H31110]
<p class=req id=H31120>
[fileformat_import_requirement H31120]
[h4 "Table B-Tree Page Format"]
<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 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=H31130>
[fileformat_import_requirement H31130]
<p class=req id=H31140>
[fileformat_import_requirement H31140]
<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 "Table B-Tree Cell Format" table_btree_cell_format]
<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>.
[Figure tablenodecell.gif figure_tablenodecell "Table B-Tree Internal Node Cell"]
<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
................................................................................
<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).
This scenario, where the entire record is
stored within the B-Tree cell, is depicted in figure
<cite>figure_tableshortrecord</cite>.
[Figure tableshortrecord.gif figure_tableshortrecord "Table B-Tree Small Record Leaf Node Cell"]
<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
................................................................................
</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>.
[Figure tablelongrecord.gif figure_tablelongrecord "Table B-Tree Large Record Leaf Node Cell"]
<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=H31150>
[fileformat_import_requirement H31150]
<p class=req id=H31160>
[fileformat_import_requirement H31160]
<p class=req id=H31170>
[fileformat_import_requirement H31170]
<p class=req id=H31180>
[fileformat_import_requirement H31180]
<p class=req id=H31190>
[fileformat_import_requirement H31190]
<p>
Requirement H31190 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 H30090 to store this value in the relevant database file
header field.
[h3 "Overflow Page Chains" "overflow_page_chains"]
<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.
[Figure overflowpage.gif figure_overflowpage "Overflow Page Format"]
<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
................................................................................
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=H31200>
[fileformat_import_requirement H31200]
<p class=req id=H31210>
[fileformat_import_requirement H31210]
<p class=req id=H31220>
[fileformat_import_requirement H31220]
<p class=req id=H31230>
[fileformat_import_requirement H31230]
[h2 "The Free Page List" free_page_list]
<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>
................................................................................
<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).
[Figure freelistpage.gif figure_freelistpage "Free List Trunk Page Format"]
<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=H31240>
[fileformat_import_requirement H31240]
<p class=req id=H31250>
[fileformat_import_requirement H31250]
<p class=req id=H31260>
[fileformat_import_requirement H31260]
<p class=req id=H31270>
[fileformat_import_requirement H31270]
<p class=req id=H31280>
[fileformat_import_requirement H31280]
<p class=req id=H31290>
[fileformat_import_requirement H31290]
<p class=req id=H31300>
[fileformat_import_requirement H31300]
<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=H31310>
[fileformat_import_requirement H31310]
<p class=req id=H31320>
[fileformat_import_requirement H31320]
[h2 "Pointer Map Pages" pointer_map_pages]
<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]
[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.
[Figure pointermapentry.gif figure_pointermapentry "Pointer Map Entry Format"]
<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:
................................................................................
database file:
<pre>
<i>pointer-map-page-number</i> := 2 + <i>n</i> * <i>num-entries</i>
</pre>
<p class=req id=H31330>
[fileformat_import_requirement H31330]
<p class=req id=H31340>
[fileformat_import_requirement H31340]
<p class=req id=H31350>
[fileformat_import_requirement H31350]
<p class=req id=H31360>
[fileformat_import_requirement H31360]
<p class=req id=H31370>
[fileformat_import_requirement H31370]
<p>
The following requirements govern the content of pointer-map entries.
<p class=req id=H31380>
[fileformat_import_requirement H31380]
<p class=req id=H31390>
[fileformat_import_requirement H31390]
<p class=req id=H31400>
[fileformat_import_requirement H31400]
<p class=req id=H31410>
[fileformat_import_requirement H31410]
<p class=req id=H31420>
[fileformat_import_requirement H31420]
[h1 "Journal File Format" journal_file_format]
<p>
This section describes the format used by an SQLite <i>journal file</i>.
<p>
A journal file consists of one or more <i>journal headers</i>, zero
or more <i>journal records</i> and optionally a <i>master journal
................................................................................
second set of zero or more <i>journal records</i> and so on. There
is no limit to the number of <i>journal headers</i> a journal file
may contain. Following the <i>journal headers</i> and their accompanying
sets of <i>journal records</i> may be the optional <i>master journal
pointer</i>. Or, the file may simply end following the final <i>journal
record</i>.
[h2 "Journal Header Format" journal_header_format]
<p>
A <i>journal header</i> is <i>sector-size</i> bytes in size, where <i>
sector-size</i> is the value returned by the xSectorSize method of
the file handle opened on the database file. Only the first 28 bytes
of the <i>journal header</i> are used, the remainder may contain garbage
data. The first 28 bytes of each <i>journal header</i> consists of an
eight byte block set to a well-known value, followed by five big-endian
32-bit unsigned integer fields.
[Figure journal_header.gif figure_journal_header "Journal Header Format"]
<p>
Figure <cite>figure_journal_header</cite> graphically depicts the layout
of a <i>journal header</i>. The individual fields are described in
the following table. The offsets in the 'byte offset' column of the
table are relative to the start of the <i>journal header</i>.
[Table]
[Tr]<th>Byte offset<th>Size in bytes<th width=100%>Description
[Tr]<td>0<td>8<td>The <b>journal magic</b> field always contains a
well-known 8-byte string value used to identify SQLite
journal files. The well-known sequence of byte values
is:
<pre>0xd9 0xd5 0x05 0xf9 0x20 0xa1 0x63 0xd7</pre>
[Tr]<td>8<td>4<td>This field, the <b>record count</b>, is set to the
number of <i>journal records</i> that follow this
<i>journal header</i> in the <i>journal file</i>.
[Tr]<td>12<td>4<td>The <b>checksum initializer</b> field is set to a
pseudo-random value. It is used as part of the
algorithm to calculate the checksum for all <i>journal
records</i> that follow this <i>journal header</i>.
[Tr]<td>16<td>4<td>This field, the <b>database page count</b>, is set
to the number of pages that the <i>database file</i>
contained before any modifications associated with
<i>write transaction</i> are applied.
[Tr]<td>20<td>4<td>This field, the <b>sector size</b>, is set to the
<i>sector size</i> of the device on which the
<i>journal file</i> was created, in bytes. This value
is required when reading the journal file to determine
the size of each <i>journal header</i>.
[Tr]<td>24<td>4<td>The <b>page size</b> field contains the database page
size used by the corresponding <i>database file</i>
when the <i>journal file</i> was created, in bytes.
</table>
<p>
All <i>journal headers</i> are positioned in the file so that they
start at a <i>sector size</i> aligned offset. To achieve this, unused
space may be left between the start of the second and subsequent
<i>journal headers</i> and the end of the <i>journal records</i>
associated with the previous header.
[h2 "Journal Record Format" journal_record_format]
<p>
Each <i>journal record</i> contains the original data for a database page
modified by the <i>write transaction</i>. If a rollback is required, then
this data may be used to restore the contents of the database page to the
state it was in before the <i>write transaction</i> was started.
[Figure journal_record.gif figure_journal_record "Journal Record Format"]
<p>
A <i>journal record</i>, depicted graphically by figure
<cite>figure_journal_record</cite>, contains three fields, as described
in the following table. Byte offsets are relative to the start of the
<i>journal record</i>.
[Table]
[Tr]<th>Byte offset<th>Size in bytes<th width=100%>Description
[Tr]<td>0<td>4<td>The page number of the database page associated with
this <i>journal record</i>, stored as a 4 byte
big-endian unsigned integer.
[Tr]<td>4<td><i>page-size<td>
This field contains the original data for the page,
exactly as it appeared in the database file before the
<i>write transaction</i> began.
[Tr]<td style="white-space: nowrap">4 + <i>page-size</i><td>4<td>
This field contains a checksum value, calculated based
on the contents of the journaled database page data
(the previous field) and the values stored in the
<i>checksum initializer</i> field of the preceding
<i>journal header</i>.
</table>
<p>
The set of <i>journal records</i> that follow a <i>journal header</i>
in a <i>journal file</i> are packed tightly together. There are no
alignment requirements for <i>journal records</i> as there are for
<i>journal headers</i>.
[h2 "Master Journal Pointer"]
<p>
To support <i>atomic</i> transactions that modify more than one
database file, SQLite sometimes includes a <i>master journal pointer</i>
record in a <i>journal file</i>. A <i>master journal pointer</i>
contains the name of a <i>master journal-file</i> along with a
check-sum and some well-known values that allow the
................................................................................
journal pointer</i> is always positioned at a <i>sector size</i>
aligned offset. If the <i>journal record</i> or <i>journal header</i>
that appears immediately before the <i>master journal pointer</i> does
not end at an aligned offset, then unused space is left between the
end of the <i>journal record</i> or <i>journal header</i> and the start
of the <i>master journal pointer</i>.
[Figure master_journal_ptr.gif figure_master_journal_ptr "Master Journal Pointer Format"]
<p>
A <i>master journal pointer</i>, depicted graphically by figure
<cite>figure_master_journal_ptr</cite>, contains five fields, as
described in the following table. Byte offsets are relative to the
start of the <i>master journal pointer</i>.
[Table]
[Tr]<th>Byte offset<th>Size in bytes<th width=100%>Description
[Tr]<td>0<td>4<td>This field, the <b>locking page number</b>, is always
set to the page number of the database <i>locking page</i>
stored as a 4-byte big-endian integer. The <i>locking page</i>
is the page that begins at byte offset 2<super>30</super> of the
database file. Even if the database file is large enough to
contain the <i>locking page</i>, the <i>locking page</i> is
never used to store any data and so the first four bytes of of a
valid <i>journal record</i> will never contain this value.
[Tr]<td>4<td><i>name-length</i><td>
The <b>master journal name</b> field contains the name of the
master journal file, encoded as a utf-8 string. There is no
nul-terminator appended to the string.
[Tr]<td>4 + <i>name-length</i><td><i>4<td>
The <b>name-length</b> field contains the length of the
previous field in bytes, formatted as a 4-byte big-endian
unsigned integer.
[Tr]<td>8 + <i>name-length</i><td><i>4<td>
The <b>checksum</b> field contains a checksum value stored as
a 4-byte big-endian signed integer. The checksum value is
calculated as the sum of the bytes that make up the <i>
master journal name</i> field, interpreting each byte as
an 8-bit signed integer.
[Tr]<td style="white-space: nowrap">12 + <i>name-length</i><td><i>8<td>
Finally, the <b>journal magic</b> field always contains a
well-known 8-byte string value; the same value stored in the
first 8 bytes of a <i>journal header</i>. The well-known
sequence of bytes is:
<pre>0xd9 0xd5 0x05 0xf9 0x20 0xa1 0x63 0xd7</pre>
</table>
<!--
\[h1 "Database File Structure Traversal" "database_file_traversal"]
\[h2 "B-Tree Cursors"]
<h2>B-Tree Access Strategies</h2>
<h3>Full Linear Scan</h3>
<h3>Seek to Value</h3>
<h3>Range Scan</h3>
<h2>Retrieving Record Values</h2>
\[h1 "Database File Manipulation" "database_file_manipulation"]
<h2>Creating a Database</h2>
<h2>Table B-Trees</h2>
<h3>Creating a new Table B-Tree</h3>
<h3>Deleting a Table B-Tree</h3>
<h3>Adding an Entry to a Table B-Tree</h3>
................................................................................
<h2>Overflow Chains</h2>
<h2>Allocating/Deallocating Pages</h2>
<h2>Allocating a Page</h2>
<h2>Deallocating a Page</h2>
<h2>Auto-Vacuum Commit Operations</h2>
<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>
................................................................................
<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 "Database Creation/Initialization" database_initialization]
<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.
................................................................................
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 "Setting Database Parameters" database_parameters]
<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,
................................................................................
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 "Table/Index Creation" btree_creation]
<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.
................................................................................
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"]
<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>
................................................................................
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"]
<p class=todo>
Finish this.
<h3>Removing Records</h3>
<p class=todo>
Finish this.
................................................................................
</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 "Page Allocation" page_allocation]
<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
................................................................................
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 "Page Deallocation" page_deallocation]
<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,
................................................................................
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 "Removing a Page From The Free List" page_removal]
<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
................................................................................
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 "Database Reorganization (auto-vacuum)" incremental_vacuum]
<p class=todo>
Requirements describing incremental vacuum steps. And on-commit
handling in auto-vacuum databases.
-->
[h1 References]
<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>
}]
</tcl>
<div id=toc>
<tcl>hd_puts $TOC</tcl>
</div id=toc>
<tcl>hd_puts [FixReferences $body]</tcl>
|