Let's don't focus on the "file format" documentation, just focus on the BTree 
algorithm.


I want to know the depth of the BTree, and how to reduce the depth of it.


________________________________
From: sqlite-users <sqlite-users-boun...@mailinglists.sqlite.org> on behalf of 
james ni <james...@live.cn>
Sent: Friday, August 11, 2017 18:08
To: SQLite mailing list
Subject: Re: [sqlite] What's the level of B+-Tree ?

Maybe we are talking the different thing.


Background of my problem:

1, When one table grows larger, I found the INSERT speed is becoming slower and 
slower;


2, My task is to make it not so slower;


3, The linux perf tool shows the BTree depth is likely growing larger and 
larger after more records are inserted because the number of syscalls are 
increasing quickly;


4, So I want to know the how many keys can be stored in a Btree node. The more 
keys that a Btree node can hold, the shorter of the Btree depth, the less 
syscalls and disk IOs;


That's what i want to know.

________________________________
From: sqlite-users <sqlite-users-boun...@mailinglists.sqlite.org> on behalf of 
Rowan Worth <row...@dug.com>
Sent: Friday, August 11, 2017 17:09
To: SQLite mailing list
Subject: Re: [sqlite] What's the level of B+-Tree ?

Jump to the byte offset specified by the "start of the cell content"
header, which comes just after the number of pages (ie. offset 0x0f90 in
your pasted example).

Cross reference the data at that offset against section "2.1 Record Format"
of the Database File Format page. By decoding the record header you know
how many columns are in that particular index record (which might not match
the number of columns are in the table, as noted in the spec).

Is that what you're after? Or are you trying to figure out the depth of a
particular btree page?

-Rowan

On 11 August 2017 at 16:51, james ni <james...@live.cn> wrote:

> Thanks, but I'm more confused now.
>
>
> As in the example that I provided, there are 4 cells in a single btree
> page. So there must be some mechanism to determine hoe many keys that one
> cell can own.
>
>
> I want to know exactly the very value and just how to change the value to
> a larger one, for example, 256, 512, or even larger.
>
> ________________________________
> From: sqlite-users <sqlite-users-boun...@mailinglists.sqlite.org> on
> behalf of Hick Gunter <h...@scigames.at>
> Sent: Friday, August 11, 2017 16:31
> To: 'SQLite mailing list'
> Subject: Re: [sqlite] What's the level of B+-Tree ?
>
> The number of keys in an sqlite index page depends on the size of the
> database pages and the size of the (compressed) key value, which is stored
> in the same "row format" as the data.
>
> Child segment pointers are stored at the beginning of the page and key
> contents are stored at the end. The page is full, when the unallocated
> space in between these areas becomes too small to store enything useful.
> Note that key contents may change in length if a key field is updated, so
> the key contents area may become fragmented (sqlite willl defragment the
> page if needed).
>
> -----Urspr√ľngliche Nachricht-----
> Von: sqlite-users [mailto:sqlite-users-boun...@mailinglists.sqlite.org]
> Im Auftrag von ni james
> Gesendet: Freitag, 11. August 2017 04:57
> An: sqlite-users@mailinglists.sqlite.org
> Betreff: [sqlite] What's the level of B+-Tree ?
>
> In the "SQLite File Format" document, the BTree layout is described, but
> now I want to know how to get the BTree level (which is the 'K' value
> mentioned in the Documentation)?
>
>
> Generally, one B+Tree segment contains K keys and (K+1) pointers to child
> segments.
>
>
> From the source code, I found such info:
>
>
> /*
> ** This constant controls how often segments are merged. Once there are
> ** FTS3_MERGE_COUNT segments of level N, they are merged into a single
> ** segment of level N+1.
> */
> #define FTS3_MERGE_COUNT 16
>
> ....
>
> /*
> ** FTS4 virtual tables may maintain multiple indexes - one index of all
> terms
> ** in the document set and zero or more prefix indexes. All indexes are
> stored
> ** as one or more b+-trees in the %_segments and %_segdir tables.
> **
> ** It is possible to determine which index a b+-tree belongs to based on
> the
> ** value stored in the "%_segdir.level" column. Given this value L, the
> index
> ** that the b+-tree belongs to is (L<<10). In other words, all b+-trees
> with
> ** level values between 0 and 1023 (inclusive) belong to index 0, all
> levels
> ** between 1024 and 2047 to index 1, and so on.
> **
> ** It is considered impossible for an index to use more than 1024 levels.
> In
> ** theory though this may happen, but only after at least
> ** (FTS3_MERGE_COUNT^1024) separate flushes of the pending-terms tables.
> */
> #define FTS3_SEGDIR_MAXLEVEL 1024
> #define FTS3_SEGDIR_MAXLEVEL_STR "1024"
>
>
> It seems the BTree level is 16 or 1024 ??
>
>
> Would any one share you knowledge on how to get this value ?
>
> Much appreciated if you can tell how to tune this value.
>
>
> Thanks!
>
> _______________________________________________
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
>
> ___________________________________________
>  Gunter Hick
> Software Engineer
> Scientific Games International GmbH
> FN 157284 a, HG Wien
> Klitschgasse 2-4, A-1130 Vienna, Austria
> Tel: +43 1 80100 0
> E-Mail: h...@scigames.at
>
> This communication (including any attachments) is intended for the use of
> the intended recipient(s) only and may contain information that is
> confidential, privileged or legally protected. Any unauthorized use or
> dissemination of this communication is strictly prohibited. If you have
> received this communication in error, please immediately notify the sender
> by return e-mail message and delete all copies of the original
> communication. Thank you for your cooperation.
>
>
> _______________________________________________
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> _______________________________________________
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Reply via email to