First, your rows are NOT "all the same size". SQLite uses a compressed format
to store values that, among other things, uses less space for smaller integers.
IIRC your records will be (values before colon are the "manifest", values after
the colon are the "payload" of a record):
(value is 0) (value is 1) (value is INT) (value is INT) : (2) (3) = 6 bytes in
length
(value is 1) (value is 1) (value is INT) (value is INT) : (2) (3) = 6 bytes in
length
(value is INT) (value is 1) (value is INT) (value is INT) : (2) (2) (3) = 7
bytes in length
...
(value is INT) (value is 1) (value is INT) (value is INT) : (127) (2) (3) = 7
bytes in length
(value is INT) (value is 1) (value is INT) (value is INT) : (127) (2) (3) = 8
bytes in length
Second, a BTree stores records in the leaf pages only, in sort order and so
that the last record of any page sorts before the first record of the next
page. Thus the "parent" page only needs to store the first key of it's "child"
pages. When a page is completely filled up, it needs to be split. If sorted
inserts (like you are performing) are detected, literature recommends splitting
90/10 so the resulting pages willl be 90% full; random inserts result in 50/50
splits, since it is equally likely which side of the spilt the next insert is
going to be.
Deleting a record only allows space to be re-used in a limited number of cases:
a) the record to be inserted "belongs" on the same page as the record deleted
b) the record to be deleted is the last one on a leaf page (and BTree software
is set up to re-use leaf pages automatically)
c) the record to be deleted causes an internal page to become empty (and BTree
Software is set up to re-use internal pages automatically)
d) the record causes 2 adjacent pages to hold less records than would fit into
1 page (and BTree Software is set up to merge adjacent pages automatically)
e) the BTree structure is "defragmented" by whatever method implemented
(implicit reload and/or cases b to d)
With your algorithm of deleting the oldest record(s) to make space for new
records at "the other end" of the list, you are excluding case a and relying on
some combination of b thru d for re-use of pages.
Similar considerations apply to the pages holding the index created by the
PRIMARY KEY clause, but the key records are smaller and data is stored in
internal nodes, so the effects are smaller..
Note the pattern:
- After the file is "full", you need a new page every 84 records (this will
change when your test exceeds 32k records)
- The number of records required to free a page drops from 109 (#of records on
first page) to 84 (#of records on sixth thru last used page)
With a "fan out" of 84, your BTree probably has a leaf level of 60 pages of 84
records each, plus 1 internal level of 1 node holding 60 pointers to leaf pages.
>Von: sqlite-users [mailto:sqlite-users-boun...@mailinglists.sqlite.org] Im
>Auftrag von Arthur Blondel
>...
>OK, I wasn't clear.
>I'm limited in space so when the DB is full (when sqlite3_exec() returns
>SQLITE_FULL when I try to insert a new row), I remove the oldest row and retry
>to insert the new one.
>The data is always the same. That's why removing one row should be enough to
>insert a new one.
>My problem is that some times I need to remove many rows to add one new one.
>...
>Following the output:
>
>...
>3959 - DB full
>3960 - 109 rows was removed
>4044 - 92 rows was removed
>4128 - 86 rows was removed
>4212 - 85 rows was removed
>4296 - 85 rows was removed
>4380 - 84 rows was removed
>4464 - 84 rows was removed
>4548 - 84 rows was removed
>4632 - 84 rows was removed
>4716 - 84 rows was removed
>4800 - 84 rows was removed
>4884 - 84 rows was removed
>4968 - 84 rows was removed
>...
___
Gunter Hick | Software Engineer | Scientific Games International GmbH |
Klitschgasse 2-4, A-1130 Vienna | FN 157284 a, HG Wien, DVR: 0430013 | (O) +43
1 80100 - 0
May be privileged. May be confidential. Please delete if not the addressee.
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
