Many hyperlinks are disabled.

Use anonymous login
to enable hyperlinks.

Overview

Comment: | Clarification and corrections to the computation of how much content spills into overflow pages in the b-tree. |
---|---|

Downloads: | Tarball | ZIP archive | SQL archive |

Timelines: | family | ancestors | descendants | both | trunk |

Files: | files | file ages | folders |

SHA1: |
e64e27e335c3d280155a670d07e62808 |

User & Date: | drh 2011-04-22 20:49:41 |

Context

2011-05-02
| ||

12:23 | Fix a typo in the FAQ reported on the mailing list. (check-in: a8df0f43ab user: drh tags: trunk) | |

2011-04-22
| ||

20:49 | Clarification and corrections to the computation of how much content spills into overflow pages in the b-tree. (check-in: e64e27e335 user: drh tags: trunk) | |

2011-04-20
| ||

11:01 | Add the "make fast" target on the makefile - for constructing documentation without the requirements matrix. Added notation to the windows DLL on the download page to mention that it is suitable for use with Ruby on Rails. (check-in: e84c9353ca user: drh tags: trunk) | |

Changes

Changes to pages/fileformat2.in.

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 |
the page type. For the following computations, let U be the usable size of a database page, the total page size less the reserved space at the end of each page. And let P be the payload size.</p> <blockquote><dl> <dt>Table B-Tree Leaf Cell:</dt> <dd><p> ^If the payload size P is less than U-36 then the entire payload is stored on the b-tree page. ^(Let M be ((U-12)*32/255)-23. If P is greater than U-35 then the number of byte stored on the b-tree page is the lessor of M+((P-M)%(U-4)) and U-35.)^ </p></dd> <dt>Table B-Tree Interior Cell:</dt> <dd><p> Interior pages of table b-trees have no payload and so there is never any payload to spill. </p></dd> <dt>Index B-Tree Leaf Or Interior Cell:</dt> <dd><p> ^If the payload size P is less than ((U-12)*64/255)-22 then the entire payload is stored on the b-tree page. ^(Let M be ((U-12)*32/255)-23. If P is greater than ((U-12)*64/255)-23 then the number of byte stored on the b-tree page is the lessor of M+((P-M)%(U-4)) and ((U-12)*64/255)-23.)^ </p></dd> </dl></blockquote> <p>The overflow thresholds are designed to give a minimum fanout of 4 for index b-trees and to make sure enough of the payload is on the b-tree page that the record header can usually be accessed without consulting an overflow page. In hindsight, the designers of the SQLite b-tree logic realize that these thresholds could have been made much simpler. However, the computations cannot be now be changed without resulting in an incompatible file format. And the current computations work well, even if they are a little complex.</p> <h3>1.6 Cell Payload Overflow Pages</h3> <p>^When the payload of a b-tree cell is too large for the b-tree page, the surplus is spilled onto overflow pages. ^Overflow pages form a linked |
| > | | > | | | | | > | |
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 |
the page type. For the following computations, let U be the usable size of a database page, the total page size less the reserved space at the end of each page. And let P be the payload size.</p> <blockquote><dl> <dt>Table B-Tree Leaf Cell:</dt> <dd><p> ^If the payload size P is less than or equal to U-35 then the entire payload is stored on the b-tree leaf page. ^(Let M be ((U-12)*32/255)-23. If P is greater than U-35 then the number of byte stored on the b-tree leaf page is the smaller of M+((P-M)%(U-4)) and U-35.)^ ^(Note that number of bytes stored on the leaf page is never less than M.)^ </p></dd> <dt>Table B-Tree Interior Cell:</dt> <dd><p> Interior pages of table b-trees have no payload and so there is never any payload to spill. </p></dd> <dt>Index B-Tree Leaf Or Interior Cell:</dt> <dd><p> ^(Let X be ((U-12)*64/255)-23). If the payload size P is less than or equal to X then the entire payload is stored on the b-tree page.)^ ^(Let M be ((U-12)*32/255)-23. If P is greater than X then the number of byte stored on the b-tree page is the smaller of M+((P-M)%(U-4)) and X.)^ ^(Note that number of bytes stored on the index page is never less than M.)^ </p></dd> </dl></blockquote> <p>The overflow thresholds are designed to give a minimum fanout of 4 for index b-trees and to make sure enough of the payload is on the b-tree page that the record header can usually be accessed without consulting an overflow page. In hindsight, the designers of the SQLite b-tree logic realize that these thresholds could have been made much simpler. However, the computations cannot be changed without resulting in an incompatible file format. And the current computations work well, even if they are a little complex.</p> <h3>1.6 Cell Payload Overflow Pages</h3> <p>^When the payload of a b-tree cell is too large for the b-tree page, the surplus is spilled onto overflow pages. ^Overflow pages form a linked |