Thanks Rick, it's much helpful for me.
After some experiments on the internal dbstat table, I have such conclusions, much appreciate if you would review them: 1, My working Background: one WITHOUT ROWID table, this table's primary key is 30 bytes; dbstat shows there are at most 110 cells in an internal Btree page; Every page size is 4096 Bytes. 2, My conclusion: 2.1, The depth of this Btree is determined by the maximum cells in the internal page. In details the Btree depth is log(110, total_records). 2.2, If the application searches some a key in the table, in the worst situation it will issue log(110, total_records) disk IOs. And every disk IO size is the same as the database page size, in my example it's 4096 Bytes. 2.3, the number of cells is determined by the size of the primary key. So if I extend the page size from 4096 Bytes to 64KB, the maximum number of cells is expected to get increased and the depth of the Btree will shrink. Is this correct ? Thanks & Best Regards, James ________________________________ From: sqlite-users <[email protected]> on behalf of Richard Hipp <[email protected]> Sent: Saturday, August 12, 2017 1:57 To: SQLite mailing list Subject: Re: [sqlite] What's the level of B+-Tree ? On 8/11/17, Scott Robison <[email protected]> wrote: > My understanding is that SQLite doesn't use the traditional definition of > b-tree because it doesn't use fixed size records/keys. It will cram as few > or as many as possible. Correct. More records crammed into one page means that fewer pages need to be read, which makes things run faster. It also means that less disk space gets used. The in-tree portion of each record is size limited to ensure that at least four records fit on each page. Otherwise, the btree might degenerate into a linked list. The tail of records that exceed the maximum in-tree record size is written onto overflow pages. For ordinary rowid tables, a traditional b-tree is used, which means that only the key is stored on intermediate pages and all the content appears in the leaves. Since the keys are always just a rowid and typically take only a few bytes, there are ordinarily a large number keys per page. You can run the sqlite3_analyzer.exe utility program (available in the "sqlite-tools-*" bundles on the https://sqlite.org/download.html page) to see the average number of SQLite Download Page<https://sqlite.org/download.html> sqlite.org (4.62 MiB) A precompiled Android library containing the core SQLite together with appropriate Java bindings, ready to drop into any Android Studio project. (4.09 MiB ... keys/page for each table and index. Or you can use the DBSTAT virtual table (https://www.sqlite.org/dbstat.html) to query for that The DBSTAT Virtual Table - SQLite Home Page<https://www.sqlite.org/dbstat.html> www.sqlite.org The DBSTAT virtual tables is a read-only eponymous virtual table that returns information about which pages of the database files are used by which tables and indexes ... information on a page-by-page basis. For indexes and WITHOUT ROWID tables, the keys can be much larger, and so the minimum-four-per-page rule is more likely to come into play. -- D. Richard Hipp [email protected] _______________________________________________ sqlite-users mailing list [email protected] http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users sqlite-users Info Page<http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users> mailinglists.sqlite.org To see the collection of prior postings to the list, visit the sqlite-users Archives. (The current archive is only available to the list ... _______________________________________________ sqlite-users mailing list [email protected] http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
