~ubuntu-branches/ubuntu/wily/sqlite3/wily

onfocus="entersearch()" onblur="leavesearch()" style="width:24ex;padding:1px 1ex; border:solid white 1px; font-size:0.9em ; font-style:italic;color:#044a64;" value="Search SQLite Docs...">

112

113

</form>

114

</div>

115

</table>

116

</div></div></div></div>

117

</td></tr></table>

118

119

120

121

122

123

124

125

126

<div style="font-size:2em;text-align:center;color:#80a796">SQLite B-Tree Module</div>

127

<div style="font-size:1.5em;margin:1em;color:#80a796">Table Of Contents</div>

128

129

130

131

<a href="#section_1">1 Document Overview</a>

132

</a></div>

133

134

135

<a href="#section_1_1">1.1 Scope and Purpose</a>

136

</a></div>

137

138

139

<a href="#section_1_2">1.2 Document and Requirements Organization</a>

140

</a></div>

141

142

143

<a href="#section_1_3">1.3 Glossary</a>

144

</a></div>

145

146

147

<a href="#section_2">2 Module Requirements</a>

148

</a></div>

149

150

151

<a href="#section_2_1">2.1 Functional Requirements</a>

152

</a></div>

153

154

155

<a href="#section_2_1_1">2.1.1 Opening and Closing Connections</a>

156

</a></div>

157

158

159

<a href="#section_2_1_2">2.1.2 New Database Image Configuration</a>

160

</a></div>

161

162

163

<a href="#hlr_transactions">2.1.3 Transaction and Savepoint Functions</a>

164

</a></div>

165

166

167

<a href="#hlr_reading_data">2.1.4 Reading From the Database Image</a>

168

</a></div>

169

170

171

<a href="#section_2_1_5">2.1.5 Writing to the Database Image</a>

172

</a></div>

173

174

175

<a href="#section_2_1_6">2.1.6 Page-Cache Configuration Requirements</a>

176

</a></div>

177

178

179

<a href="#section_2_1_7">2.1.7 Multi-User Database Requirements</a>

180

</a></div>

181

182

183

<a href="#section_2_1_8">2.1.8 Backup/Vacuum API Requirements</a>

184

</a></div>

185

186

187

<a href="#section_2_1_9">2.1.9 Integrity Check Requirements</a>

188

</a></div>

189

190

191

<a href="#section_2_2">2.2 Other Requirements and Constraints</a>

192

</a></div>

193

194

195

<a href="#hlr_memory">2.2.1 Caching and Memory Management Requirements</a>

196

</a></div>

197

198

199

<a href="#section_2_2_2">2.2.2 Exception Handling Requirements</a>

200

</a></div>

201

202

203

<a href="#section_2_2_3">2.2.3 Well-Formedness Requirements</a>

204

</a></div>

205

206

207

<a href="#section_3">3 Module API</a>

208

</a></div>

209

210

211

<a href="#section_3_1">3.1 Opening and Closing Connections</a>

212

</a></div>

213

214

215

<a href="#section_3_1_1">3.1.1 sqlite3BtreeOpen</a>

216

</a></div>

217

218

219

<a href="#section_3_1_2">3.1.2 sqlite3BtreeClose</a>

220

</a></div>

221

222

223

<a href="#section_3_2">3.2 Database Image Configuration</a>

224

</a></div>

225

226

227

<a href="#section_3_3">3.3 Connection Configuration</a>

228

</a></div>

229

230

231

<a href="#section_3_4">3.4 Query Interfaces</a>

232

</a></div>

233

234

235

<a href="#section_3_5">3.5 Mutex Functions</a>

236

</a></div>

237

238

239

<a href="#section_3_6">3.6 Transaction and Savepoint API</a>

240

</a></div>

241

242

243

<a href="#section_3_7">3.7 Reading and Traversing the Database Image</a>

244

</a></div>

245

246

247

<a href="#section_3_7_1">3.7.1 sqlite3BtreeMovetoUnpacked</a>

248

</a></div>

249

250

251

<a href="#section_3_7_2">3.7.2 sqlite3BtreeGetMeta</a>

252

</a></div>

253

254

255

<a href="#section_3_8">3.8 Modifying the Database Image</a>

256

</a></div>

257

258

259

<a href="#sqlite3BtreeCreateTable">3.8.1 sqlite3BtreeCreateTable</a>

260

</a></div>

261

262

263

<a href="#sqlite3BtreeDropTable">3.8.2 sqlite3BtreeDropTable</a>

264

</a></div>

265

266

267

<a href="#sqlite3BtreeClearTable">3.8.3 sqlite3BtreeClearTable</a>

268

</a></div>

269

270

271

<a href="#sqlite3BtreeCursorHasMoved">3.8.4 sqlite3BtreeCursorHasMoved</a>

272

</a></div>

273

274

275

<a href="#sqlite3BtreePutData">3.8.5 sqlite3BtreePutData</a>

276

</a></div>

277

278

279

<a href="#sqlite3BtreeUpdateMeta">3.8.6 sqlite3BtreeUpdateMeta</a>

280

</a></div>

281

282

283

<a href="#sqlite3BtreeDelete">3.8.7 sqlite3BtreeDelete</a>

284

</a></div>

285

286

287

<a href="#section_3_8_8">3.8.8 sqlite3BtreeInsert</a>

288

</a></div>

289

290

291

<a href="#sqlite3BtreeIncrVacuum">3.8.9 sqlite3BtreeIncrVacuum</a>

292

</a></div>

293

294

295

<a href="#section_3_9">3.9 Advisory B-Tree Locks</a>

296

</a></div>

297

298

299

<a href="#section_3_9_1">3.9.1 sqlite3BtreeLockTable</a>

300

</a></div>

301

302

303

<a href="#section_3_9_2">3.9.2 sqlite3BtreeSchemaLocked</a>

304

</a></div>

305

306

307

<a href="#section_3_10">3.10 What do these do?</a>

308

</a></div>

309

310

311

<a href="#section_3_11">3.11 APIs not branded sqlite3BtreeXXX()</a>

312

</a></div>

313

314

315

<a href="#section_4">4 Module Implementation</a>

316

</a></div>

317

318

319

<a href="#section_4_1">4.1 Database Image Traversal</a>

320

</a></div>

321

322

323

<a href="#section_4_2">4.2 Database Image Manipulation</a>

324

</a></div>

325

326

327

<a href="#section_4_2_1">4.2.1 Creating a B-Tree Structure</a>

328

</a></div>

329

330

331

<a href="#section_4_2_2">4.2.2 Clearing a B-Tree Structure</a>

332

</a></div>

333

334

335

<a href="#section_4_2_3">4.2.3 Deleting a B-Tree Structure</a>

336

</a></div>

337

338

339

<a href="#section_4_2_4">4.2.4 Inserting, Replacing and Deleting B-Tree Entries</a>

340

</a></div>

341

342

343

<a href="#section_4_2_4_1">4.2.4.1 B-Tree Insert/Replace Entry</a>

344

</a></div>

345

346

347

<a href="#section_4_2_4_2">4.2.4.2 B-Tree Delete Entry</a>

348

</a></div>

349

350

351

<a href="#btree_balancing_algorithm">4.2.5 B-Tree Balancing Algorithm</a>

352

</a></div>

353

354

355

<a href="#section_4_2_5_1">4.2.5.1 Balance Deeper</a>

356

</a></div>

357

358

359

<a href="#section_4_2_5_2">4.2.5.2 Balance Shallower</a>

360

</a></div>

361

362

363

<a href="#section_4_2_5_3">4.2.5.3 Balance Quick</a>

364

</a></div>

365

366

367

<a href="#balance_siblings">4.2.5.4 Balance Siblings</a>

368

</a></div>

369

370

371

<a href="#section_4_2_6">4.2.6 Page Allocation and Deallocation</a>

372

</a></div>

373

374

375

<a href="#free_overflow_chain">4.2.6.1 Moving an overflow-chain to the free-list</a>

376

</a></div>

377

378

379

<a href="#section_4_2_7">4.2.7 Incremental Vacuum Step</a>

380

</a></div>

381

382

383

<a href="#section_4_3">4.3 Transactions and Savepoints</a>

384

</a></div>

385

386

387

<a href="#section_5">5 References</a>

388

</a></div>

389

390

</div id>

391

392

393

<h1 id="section_1">1 Document Overview</h1>

394

395

396

<h2 id="section_1_1">1.1 Scope and Purpose</h2>

397

398

399

<p>

400

This document provides a description of the functionality of and public

401

interface offered by the SQLite b-tree module. It also, to a certain extent,

402

describes the algorithm and implementation techniques used internally by

403

the module.

404

405

<ul>

406

<li><p> To make it easier to maintain, test and improve this critical

407

sub-system of the SQLite software library.

408

409

<li><p> To facilitate development of compatible backend modules that can

410

be used with other SQLite sub-systems, either for experimental or

411

production purposes.

412

</ul>

413

414

<p>

415

It is important to note that, even given the second bullet point above,

416

the interfaces and sub-systems described in this document are not stable.

417

They may be changed in any way with each new SQLite release. Any

418

external software development that uses these interfaces must be prepared

419

to adapt to interface refactoring without notice.

420

421

<h2 id="section_1_2">1.2 Document and Requirements Organization</h2>

422

423

424

425

Change the following so that those requirements that describe the API

426

are "low-level" requirements.

427

428

429

<tr style="text-align:left"> <th> Requirement ids <th> Contents

430

<tr style="text-align:left;background-color:#DDDDDD"> <td> H50**** <td> Requirement statements specifying the functionality required of the B-Tree module.

431

<tr style="text-align:left"> <td> H51**** <td> Requirement statements specifying the API provided by the B-Tree module.

432

<tr style="text-align:left;background-color:#DDDDDD"> <td> L****** <td> Requirement statements specifying some details of the internal workings of the B-Tree module.

433

</table>

434

435

<h2 id="section_1_3">1.3 Glossary</h2>

436

437

438

439

<tr><td class=defn><a name="glossary_Balance-Siblings_Algorithm"></a><a class=defnlink href="#glossary_Balance-Siblings_Algorithm">Balance-Siblings Algorithm</a> <td>

440

The <a class=defnlink href="#glossary_Balance-Siblings_Algorithm">balance-siblings algorithm</a> is one of four algorithms that may be used

441

used to redistribute data within a b-tree structure after an insert or

442

delete operation that causes a b-tree node to become overfull or underfull.

443

See section <cite><a href="#balance_siblings" title="Balance Siblings">4.2.5.4</a></cite> for details.

444

445

<tr><td class=defn><a name="glossary_B-Tree_Cursor"></a><a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree Cursor</a> <td>

446

<span class=todo>Define this.

447

448

<tr><td class=defn><a name="glossary_B-Tree_Database_Connection"></a><a class=defnlink href="#glossary_B-Tree_Database_Connection">B-Tree Database Connection</a> <td>

449

A <a class=defnlink href="#glossary_B-Tree_Database_Connection">B-Tree database connection</a> is a single client connection to an in-memory

450

<a class=defnlink href="#glossary_Page_cache">page cache</a>, through which a single temporary or <a class=defnlink href="#glossary_Persistent_database">persistent database</a> may

451

be accessed. This term is used throughout this document to avoid confusing

452

such connections with SQL level SQLite client connections, which are

453

sometime simply termed "database connections".

454

455

<tr><td class=defn><a name="glossary_Lazy-write_cache"></a><a class=defnlink href="#glossary_Lazy-write_cache">Lazy-write cache</a> <td>

456

<span class=todo>Define this.

457

458

<tr><td class=defn><a name="glossary_Overflow_Cell"></a><a class=defnlink href="#glossary_Overflow_Cell">Overflow Cell</a> <td>

459

<span class=todo>Define this.

460

461

<tr><td class=defn><a name="glossary_Page_cache"></a><a class=defnlink href="#glossary_Page_cache">Page cache</a> <td>

462

<span class=todo>Define this.

463

464

<tr><td class=defn><a name="glossary_Persistent_database"></a><a class=defnlink href="#glossary_Persistent_database">Persistent database</a> <td>

465

<span class=todo>Define this.

466

467

<tr><td class=defn><a name="glossary_Read-through_cache"></a><a class=defnlink href="#glossary_Read-through_cache">Read-through cache</a> <td>

468

<span class=todo>Define this.

469

470

<tr><td class=defn><a name="glossary_Shared-cache_mode"></a><a class=defnlink href="#glossary_Shared-cache_mode">Shared-cache mode</a> <td>

471

<span class=todo>Define this.

472

473

<tr><td class=defn><a name="glossary_SQLite_Error_Code"></a><a class=defnlink href="#glossary_SQLite_Error_Code">SQLite Error Code</a> <td>

474

<span class=todo>Define this.

475

476

<tr><td class=defn><a name="glossary_Temporary_database"></a><a class=defnlink href="#glossary_Temporary_database">Temporary database</a> <td>

477

<span class=todo>Define this.

478

479

</table>

480

481

482

<h1 id="section_2">2 Module Requirements</h1>

483

484

485

<p>

486

The SQLite B-Tree module, the software module described by this document,

487

is designed to query and modify a database stored using the database image

488

format described in <cite><a href="#ref_file_format" title="">[1]</a></cite>. Database images may

489

exist only in volatile main-memory (in-memory databases), or may be stored

490

persistently within the file-system (also described in

491

<cite><a href="#ref_file_format" title="">[1]</a></cite>). Or, a database image may be stored primarily

492

in main-memory with the file-system used as secondary storage if the

493

database image grows too large. Database images stored only in main-memory,

494

and those stored primarily in main-memory with the file-system used only to

495

provide secondary storage space are known collectively as <a class=defnlink href="#glossary_Temporary_database">temporary

496

databases</a>. Database images stored persistently in the file-system are termed

497

<a class=defnlink href="#glossary_Persistent_database">persistent databases</a>.

498

499

<p>

500

This module implements an in-memory <a class=defnlink href="#glossary_Page_cache">page cache</a> to manage database image

501

content. The size of the pages managed by the cache are the same as the

502

page-size of the database image. When operating on a <a class=defnlink href="#glossary_Persistent_database">persistent database</a>,

503

the cache operates as a read-through, <a class=defnlink href="#glossary_Lazy-write_cache">lazy-write cache</a>. When committing a

504

database transaction, the user explicitly directs the cache to flush all

505

dirty pages through to persistent storage. A single in-memory <a class=defnlink href="#glossary_Page_cache">page cache</a>

506

used to access the content of a <a class=defnlink href="#glossary_Persistent_database">persistent database</a> may support multiple

507

logical client connections. <span class=todo>Some brief explanation of what

508

this means. And maybe a pointer to the "Multi-User Database Requirements"

509

section.</span>

510

511

<p>

512

When operating on a <a class=defnlink href="#glossary_Temporary_database">temporary database</a>, there may only be one client for

513

each <a class=defnlink href="#glossary_Page_cache">page cache</a>. Depending on the SQLite configuration, either the database

514

or journal file, or both, may be omitted from the system.

515

516

517

518

519

520

<p><i>Figure 1 - Role of <a class=defnlink href="#glossary_Page_cache">Page Cache</a></i>

521

</center>

522

523

524

<p>

525

Figure <cite><a href="#figure_overview" title="Role of Page Cache">1</a></cite> depicts...

526

527

<p><i>

528

Roughly what is encapsulated by the module.

529

</i>

530

531

<h2 id="section_2_1">2.1 Functional Requirements</h2>

532

533

534

<p>

535

This section contains requirements describing the functionality required

536

from the B-Tree module.

537

538

539

Figure out where integrity-check goes.

540

541

<h3 id="section_2_1_1">2.1.1 Opening and Closing Connections</h3>

542

543

544

<p>

545

The B-Tree module provides an interface to open new <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connections</a>.

546

547

<p class=req id=H50010><span>The B-Tree module shall provide an interface to open a connection

548

to either a named <a class=defnlink href="#glossary_Persistent_database">persistent database</a> file, or an anonymous <a class=defnlink href="#glossary_Temporary_database">temporary

549

database</a>.</span> (C: * <a class=reqlink href=#H51001>H51001</a>)</p>

550

<p class=req id=H50020><span>When opening a <a class=defnlink href="#glossary_Persistent_database">persistent database</a>, the B-Tree module shall allow the user

551

to specify that the connection be opened for read-only access.</span></p>

552

<p class=req id=H50030><span>When opening a <a class=defnlink href="#glossary_Persistent_database">persistent database</a>, the B-Tree module shall allow the user

553

to specify that the connection only be opened if the specified file exists.</span></p>

554

<p class=req id=H50040><span>If SQLite is configured to run in <a class=defnlink href="#glossary_Shared-cache_mode">shared-cache mode</a>, and a connection is opened

555

to a <a class=defnlink href="#glossary_Persistent_database">persistent database</a> file for which there exists already a <a class=defnlink href="#glossary_Page_cache">page-cache</a> within

556

the current processes address space, then the connection opened shall be a

557

connection to the existing <a class=defnlink href="#glossary_Page_cache">page-cache</a>.</span></p>

558

<p class=req id=H50050><span>If a new <a class=defnlink href="#glossary_B-Tree_Database_Connection">B-Tree database connection</a> is opened and requirement <a class=reqlink href=#H50040>H50040</a> does not apply,

559

then a new <a class=defnlink href="#glossary_Page_cache">page-cache</a> shall be created within the processes address space. The

560

opened connection shall be a connection to the new <a class=defnlink href="#glossary_Page_cache">page-cache</a>.</span></p>

561

562

<p>

563

The B-Tree module also provides an interface to close existing <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database

564

connections</a>.

565

566

<p class=req id=H50060><span>The B-Tree module shall provide an interface to close a <a class=defnlink href="#glossary_B-Tree_Database_Connection">B-Tree database connection</a>.</span></p>

567

<p class=req id=H50070><span>If a <a class=defnlink href="#glossary_B-Tree_Database_Connection">B-Tree database connection</a> is closed and this causes the associated

568

<a class=defnlink href="#glossary_Page_cache">page-cache</a> to have zero connections to it, then the <a class=defnlink href="#glossary_Page_cache">page-cache</a> shall be closed

569

and all associated resources released.</span></p>

570

571

<h3 id="section_2_1_2">2.1.2 New Database Image Configuration</h3>

572

573

574

<p>

575

The following requirements describe database configuration options that

576

are only applicable to new database images. For the purposes of the

577

following requirements, a "new database image" is defined as one that is

578

zero pages in size.

579

580

<p class=req id=H50080><span>The B-Tree module shall provide an interface to configure the page-size of a

581

new database image.</span></p>

582

<p class=req id=H50090><span>The B-Tree module shall provide an interface to configure whether or not a new

583

database image is auto-vacuum capable.</span></p>

584

585

<h3 id="hlr_transactions">2.1.3 Transaction and Savepoint Functions</h3>

586

587

588

589

This needs a lot of work...

590

591

<p>

592

All read and write operations performed on a database image via the

593

B-Tree module interfaces occur within the context of a read or write

594

transaction. <span class=todo>Something about the ACID nature of

595

transactions and how this applies to read and write transactions</span>)

596

597

<p class=req id=H50100><span>The B-Tree module shall provide an interface to open (start) a read-only transaction.</span></p>

598

<p class=req id=H50101><span>The B-Tree module shall provide an interface to close (finish) a read-only transaction.</span></p>

599

600

<p>

601

Read/write:

602

603

<p class=req id=H50102><span>The B-Tree module shall provide an interface to open a read/write transaction

604

or to upgrade from a read-only transaction to a read/write transaction.</span></p>

605

<p class=req id=H50103><span>The B-Tree module shall provide an interface to commit a read/write transaction.</span></p>

606

<p class=req id=H50104><span>The B-Tree module shall provide an interface to rollback a read/write transaction.</span></p>

607

608

609

Multi-file transaction support.

610

611

<p>

612

Transaction state query:

613

<p class=req id=H50108><span>The B-Tree module shall provide an interface to query a <a class=defnlink href="#glossary_B-Tree_Database_Connection">B-Tree database

614

connection</a> to determine if there is an open transaction, and if so if the open

615

transaction is read-only or read/write.</span></p>

616

617

<p>

618

Savepoints:

619

620

621

Define "savepoint transactions" and fix the following requirements.

622

623

<p class=req id=H50105><span>The B-Tree module shall provide an interface to open savepoint transactions.</span></p>

624

<p class=req id=H50106><span>The B-Tree module shall provide an interface to commit savepoint transactions.</span></p>

625

<p class=req id=H50107><span>The B-Tree module shall provide an interface to rollback savepoint transactions.</span></p>

626

627

<h3 id="hlr_reading_data">2.1.4 Reading From the Database Image</h3>

628

629

630

<p>

631

The B-Tree module allows the user to read a subset of the fields from the

632

database image header. Each such field is stored in the header as a 4-byte

633

unsigned big-endian integer. A complete description of each field and its

634

interpretation may be found in <cite><a href="#ref_file_format" title="">[1]</a></cite>.

635

636

<p class=req id=H50109><span>The B-Tree module shall provide an interface to read the value of any of the

637

4-byte unsigned big-endian integer fields beginning at byte offset 36 of the

638

database image.</span> (C: <a class=reqlink href=#H51015>H51015</a> <a class=reqlink href=#H51016>H51016</a> <a class=reqlink href=#H51017>H51017</a>)</p>

639

640

<p>

641

In other words, the database image header fields that may be read via

642

this module are:

643

644

<ul>

645

<li> The number of free pages in the database image,

646

<li> The database image schema version (schema cookie).

647

<li> The database image schema layer file-format.

648

<li> The default <a class=defnlink href="#glossary_Page_cache">page-cache</a> size.

649

<li> The "auto-vacuum last root-page" field.

650

<li> The database image text-encoding field.

651

<li> The database image user-cookie value.

652

<li> The database image incremental-vacuum flag.

653

</ul>

654

655

<p>

656

With the exception of the database image header fields described above,

657

all data is read from the database image using <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree cursors</a>. A <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree

658

cursor</a> is a control structure for traversing the contents of a single

659

table or index b-tree structure within a database image. As well as

660

"forward" and "back" operations, a <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree cursor</a> supports fast seeking to

661

a table entry identified by key value, or to the first or last entry in

662

the table.

663

664

<p>

665

When a <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree cursor</a> is created, the specific table or index b-tree that

666

it is used to traverse is identified by the database image page number

667

of its root page. Since the root-page of the schema table is always page

668

1, and the contents of the schema table includes the root page numbers of all

669

other index and table b-tree structures in the database image, it is

670

possible for the application to determine the set of valid root-page

671

numbers by first traversing the schema table.

672

673

<p class=req id=H50110><span>The B-Tree module shall provide an interface to open a <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree cursor</a> on any table or

674

index b-tree within the database image, given its root page number.</span></p>

675

<p class=req id=H50111><span>The B-Tree module shall provide an interface to close a <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree cursor</a>.</span></p>

676

<p class=req id=H50112><span>The B-Tree module shall provide an interface to move an open <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree cursor</a> to

677

the entry associated with the largest key in the open b-tree structure.</span></p>

678

<p class=req id=H50113><span>The B-Tree module shall provide an interface to move an open <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree cursor</a> to

679

the entry associated with the smallest key in the open b-tree structure.</span></p>

680

<p class=req id=H50114><span>The B-Tree module shall provide an interface to move an open <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree cursor</a> that

681

currently points at a valid b-tree entry to the next entry in the b-tree

682

structure, sorted in order of key value, if any.</span></p>

683

<p class=req id=H50115><span>The B-Tree module shall provide an interface to move an open <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree cursor</a> that

684

currently points at a valid b-tree entry to the previous entry in the b-tree

685

structure, sorted in order of key value, if any.</span></p>

686

<p class=req id=H50116><span>The B-Tree module shall provide an interface to retrieve the key value

687

associated with the b-tree structure entry that a <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree cursor</a> is pointing to,

688

if any.</span></p>

689

<p class=req id=H50117><span>The B-Tree module shall provide an interface to retrieve the blob of data (the

690

database record) associated with the b-tree structure entry that a <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree

691

cursor</a> open on a table b-tree is pointing to, if any.</span></p>

692

<p class=req id=H50118><span>The B-Tree module shall provide an interface to return the number of entries

693

currently stored in the b-tree structure that a <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree cursor</a> is open on.</span></p>

694

695

<p>

696

As well as traversing a b-tree structure using the operations enumerated

697

by the above requirements, it is also possible to use a cursor to search

698

a b-tree structure for a specified key value. If the key value can be

699

found, the cursor is left pointing at the entry with the specified key

700

value. Otherwise, the cursor is left pointing at either the entry with the

701

largest key that is smaller than the specified key, or to the entry with

702

the smallest key that is larger than the specified key. For table b-tree

703

structures, where the key values are 64-bit integers, the definition of

704

smaller, larger and equal to is straightforward. For index b-tree

705

structures, where the key values are database records, the manner in

706

which key values must be compared is more complicated. Refer to

707

<cite><a href="#ref_file_format" title="">[1]</a></cite> for a full explanation.

708

709

710

There is a specific section in <cite><a href="#ref_file_format" title="">[1]</a></cite> devoted to

711

record sort order in index b-tree structures. There needs to be some way to

712

point to it. Or, better, to the requirement or range of requirements.

713

714

715

Maybe a system that automatically links text like H30100 to the

716

corresponding requirement. Within a document if it can find it, or a

717

summary page (hlreq.html for example).

718

719

720

<p class=req id=H50119><span>Given a key value, the B-Tree module shall provide an interface to move a

721

<a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree cursor</a> open on a b-tree structure to the B-Tree entry with the matching

722

key value, if such an entry exists.</span></p>

723

<p class=req id=H50120><span>If the interface required by <a class=reqlink href=#H50119>H50119</a> is used to search for a key value that is

724

not present in the b-tree structure and the b-tree is not empty, the cursor shall

725

be moved to an existing entry that would be adjacent to a hypothetical

726

entry with the specified key value.</span></p>

727

<p class=req id=H50121><span>The interface required by <a class=reqlink href=#H50119>H50119</a> shall provide an indication to the caller as

728

to whether the cursor is left pointing at an entry with a key value that is

729

smaller, larger or equal to the requested value, or if it is pointing to no

730

entry at all (because the b-tree structure is empty).</span></p>

731

732

733

Does it depend on the structure of the tree whether the cursor is left

734

pointing to a smaller or larger entry after a failed search? Or is it

735

possible to determine which it will be based only on the set of keys

736

stored in the tree?

737

738

<p>

739

As well as the standard search operation described by the above

740

requirements, cursors open on index b-tree structures are required to

741

support several variants, as follows:

742

743

<ul>

744

<li> <b>Ignore rowid search mode</b>. The final value in a database

745

record used as an index-btree key is always an integer "rowid"

746

field. A search in this mode proceeds as if each key in the b-tree

747

was missing this field.

748

749

<li> <b>Increment key mode</b>.

750

<li> <b>Prefix match mode</b>.

751

<li> <b>Prefix search mode</b>.

752

</ul>

753

754

755

Finish the bullet points above and add HLR for each search mode.

756

757

<p>

758

More than one cursor can be open on a single b-tree structure at one time.

759

It is also possible for a write-cursor to modify the contents of a b-tree

760

structure while other cursors are open on it. The b-tree module does not

761

include any type of row-locking mechanism. It is possible for a write-cursor

762

to be used to delete an entry from a b-tree structure even if there are

763

one or more other cursors currently pointing to the entry being deleted.

764

765

766

Requirements to do with how the above is handled. Traceability to

767

sqlite3BtreeCursorHasMoved is required.

768

769

<h3 id="section_2_1_5">2.1.5 Writing to the Database Image</h3>

770

771

772

<p>

773

The B-Tree module allows the user to write values to a subset of the

774

fields from the database image header. The set of writable fields is

775

the same as the set of fields enumerated in section

776

<cite><a href="#hlr_reading_data" title="Reading From the Database Image">2.1.4</a></cite> that the B-Tree module is required to

777

provide read access to by requirement <a class=reqlink href=#H50109>H50109</a>.

778

779

<p class=req id=H50122><span>The B-Tree module shall provide an interface to write a value to any of the

780

4-byte unsigned big-endian integer fields beginning at byte offset 36 of the

781

database image.</span></p>

782

783

<p>

784

The B-Tree module also supports operations to create new b-tree

785

structures within the database image. Existing b-tree structures may be

786

deleted from the database image entirely, or their entire contents may be

787

deleted, leaving an empty b-tree structure.

788

789

<p class=req id=H50123><span>The B-Tree module shall provide an interface to create a new index or table

790

b-tree structures within the database image. The interface shall automatically

791

assign a root-page to the new b-tree structure.</span></p>

792

<p class=req id=H50124><span>The B-Tree module shall provide an interface to remove an existing index or

793

table b-tree structure from the database image, given the root page number of

794

the b-tree to remove.</span></p>

795

<p class=req id=H50125><span>The B-Tree module shall provide an interface to remove all entries from (delete

796

the contents of) an index or table b-tree, given the root page number of the

797

b-tree to empty.</span></p>

798

799

<p>

800

As one would expect, the B-Tree module also provides an interface to

801

insert and delete entries from b-tree structures. These operations are

802

performed using a B-Tree write cursor, a special type of <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree cursor</a>

803

(see section <cite><a href="#hlr_reading_data" title="Reading From the Database Image">2.1.4</a></cite>).

804

805

<p class=req id=H50126><span>When opening a <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree cursor</a> using the interface required by <a class=reqlink href=#H50110>H50110</a>, it shall

806

be possible to specify that the new cursor be a write cursor, or an ordinary

807

read-only cursor.</span></p>

808

<p class=req id=H50127><span>The B-Tree module shall provide an interface that allows the user to delete the

809

b-tree entry that a write cursor points to, if any.</span> (C: <a class=reqlink href=#L50013>L50013</a>)</p>

810

<p class=req id=H50128><span>The B-Tree module shall provide an interface to insert new entries into a table

811

or index B-Tree, given a write cursor open on the table or index b-tree the new

812

entry is to be inserted into.</span> (C: <a class=reqlink href=#L50001>L50001</a> <a class=reqlink href=#L50002>L50002</a> <a class=reqlink href=#L50003>L50003</a> <a class=reqlink href=#L50004>L50004</a> <a class=reqlink href=#L50012>L50012</a>)</p>

813

814

815

Incremental vacuum step.

816

817

<h3 id="section_2_1_6">2.1.6 <a class=defnlink href="#glossary_Page_cache">Page-Cache</a> Configuration Requirements</h3>

818

819

820

<p>

821

A <a class=defnlink href="#glossary_Page_cache">page-cache</a> has a number of operational parameters that may be configured

822

at run-time via an open <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a>. Note that even though the

823

interfaces provided by this module allow these parameters to be set via a

824

<a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a>, they are properties of the <a class=defnlink href="#glossary_Page_cache">page-cache</a>, not

825

the <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a>. In situations where more than one <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree

826

database connection</a> is connected to a single <a class=defnlink href="#glossary_Page_cache">page-cache</a>, writes made via

827

one <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> may overwrite the values set by another.

828

The following table summarizes the available configuration parameters.

829

830

831

<tr style="text-align:left"> <th>Parameter <th>Description <th>Requirements

832

<tr style="text-align:left;background-color:#DDDDDD"> <td>Locking-mode

833

834

835

<tr style="text-align:left"> <td>Journal-mode

836

837

838

<tr style="text-align:left;background-color:#DDDDDD"> <td>Journal-file size limit

839

<td>The journal-file size limit parameter may be set to any integer

840

value within the range of a 64-bit signed integer. Any negative

841

values is interpreted as "no limit". Otherwise, if the

842

journal-file size limit is set to zero or a positive number, it

843

represents an upper limit on the size of the journal file in

844

bytes. If the application executes a database write operation that

845

would normally cause the journal file to grow larger than this

846

configured limit, the operation fails and an error is returned

847

to the user. The default value of this parameter is -1 (no

848

limit).

849

850

<tr style="text-align:left"> <td style="white-space:nowrap">Database-file size limit

851

<td>The database-image size limit parameter may be set to any integer

852

value greater than zero within the range of a 32-bit signed

853

integer. The configured value represents an upper limit on the size of

854

the database image in pages. If the application executes a

855

database write operation that would normally cause the database image to

856

grow larger than this configured limit, the operation fails and

857

an error is returned to the user.

858

859

<tr style="text-align:left;background-color:#DDDDDD"> <td>Cache size

860

<td>The cache-size parameter may be set to any integer value. How it

861

affects operation depends on the specific P-Cache implementation used

862

by the <a class=defnlink href="#glossary_Page_cache">page-cache</a>. <span class=todo>Refer to details for the

863

behaviour of the built-in default P-Cache.</span>

864

865

<tr style="text-align:left"> <td>Safety level

866

<td>The safety-level parameter may be set to "none", "normal" or "full".

867

<span class=todo> Where will the effect of this defined/required?</span>

868

869

</table>

870

871

<p class=req id=H50138><span>The B-Tree module shall provide an interface allowing the application to set

872

the locking-mode of a <a class=defnlink href="#glossary_Page_cache">page-cache</a> to either "normal" or "exclusive", given an

873

open <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> to that <a class=defnlink href="#glossary_Page_cache">page-cache</a>.</span></p>

874

<p class=req id=H50139><span>If the locking-mode of a <a class=defnlink href="#glossary_Page_cache">page-cache</a> is set to "normal" when a read/write

875

or read-only transaction is ended, any locks held on the database file-system

876

representation by the <a class=defnlink href="#glossary_Page_cache">page-cache</a> shall be relinquished.</span></p>

877

<p class=req id=H50140><span>If the locking-mode of a <a class=defnlink href="#glossary_Page_cache">page-cache</a> is set to "exclusive" when a read/write

878

or read-only transaction is ended, any locks held on the database file-system

879

representation by the <a class=defnlink href="#glossary_Page_cache">page-cache</a> shall be retained.</span></p>

880

881

882

And if a read/write transaction is downgraded to a read-only transaction?

883

This scenario should also be dealt with in section <cite><a href="#hlr_transactions" title="Transaction and Savepoint Functions">2.1.3</a></cite>.

884

885

<p class=req id=H50141><span>The B-Tree module shall provide an interface allowing the application to set

886

the journal-mode of a <a class=defnlink href="#glossary_Page_cache">page-cache</a> to one of "off", "memory", "delete",

887

"persist", or "truncate", given an open <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> to that

888

<a class=defnlink href="#glossary_Page_cache">page-cache</a>.</span></p>

889

<p class=req id=H50142><span>If the journal-mode of a <a class=defnlink href="#glossary_Page_cache">page-cache</a> is set to "off" when a read/write

890

transaction is opened, then the transaction shall use no journal file.</span></p>

891

<p class=req id=H50143><span>If the journal-mode of a <a class=defnlink href="#glossary_Page_cache">page-cache</a> is set to "memory" when a read/write

892

transaction is opened, then instead of using the journal file located in the

893

file-system, journal-file data shall be stored in main-memory.</span></p>

894

<p class=req id=H50144><span>If the journal-mode of a <a class=defnlink href="#glossary_Page_cache">page-cache</a> is set to "delete" when a read/write

895

transaction is opened, then any journal file used by the transaction shall

896

be deleted at the conclusion of the transaction.</span></p>

897

<p class=req id=H50145><span>If the journal-mode of a <a class=defnlink href="#glossary_Page_cache">page-cache</a> is set to "truncate" when a read/write

898

transaction is opened, then any journal file used by the transaction shall

899

be truncated to zero bytes in size at the conclusion of the transaction.</span></p>

900

<p class=req id=H50146><span>If the journal-mode of a <a class=defnlink href="#glossary_Page_cache">page-cache</a> is set to "persist" when a read/write

901

transaction is opened, then any journal file used by the transaction shall

902

remain in the file-system at the conclusion of the transaction.</span></p>

903

904

905

The difference in functionality provided by "off", "memory" and the 3

906

modes that use a real journal file should also feature in

907

<cite><a href="#hlr_transactions" title="Transaction and Savepoint Functions">2.1.3</a></cite>.

908

909

<p class=req id=H50147><span>The B-Tree module shall provide an interface to set the value of the

910

journal-file size limit configuration parameter of a <a class=defnlink href="#glossary_Page_cache">page-cache</a>, given

911

an open <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> to that <a class=defnlink href="#glossary_Page_cache">page-cache</a>.</span></p>

912

<p class=req id=H50148><span>The default value assigned to the journal-file size limit configuration of a

913

<a class=defnlink href="#glossary_Page_cache">page-cache</a> shall be -1.</span></p>

914

<p class=req id=H50149><span>If the journal-file size limit parameter is set to a non-negative value, and

915

the user executes a write operation that would otherwise require the journal

916

file to be extended to a size greater than the configured value in bytes, then

917

the operation shall fail and an error be returned to the user.</span></p>

918

919

<p class=req id=H50150><span>The B-Tree module shall provide an interface to set the value of the

920

database-image size limit configuration parameter of a <a class=defnlink href="#glossary_Page_cache">page-cache</a>, given

921

an open <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> to that <a class=defnlink href="#glossary_Page_cache">page-cache</a>.</span></p>

922

<p class=req id=H50151><span>The default value assigned to the database-image size limit configuration of a

923

<a class=defnlink href="#glossary_Page_cache">page-cache</a> shall be the value of the compile time symbol SQLITE_MAX_PAGE_COUNT

924

(1073741823 by default).</span></p>

925

<p class=req id=H50152><span>If the database-image size limit parameter is set to a non-negative value, and

926

the user executes a write operation that would otherwise require the journal

927

file to be extended to a size greater than the configured value in bytes, then

928

the operation shall fail and an error be returned to the user.</span></p>

929

930

<p class=req id=H50153><span>The B-Tree module shall provide an interface to set the value of the

931

cache-size configuration parameter of a <a class=defnlink href="#glossary_Page_cache">page-cache</a>, given an open <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree

932

database connection</a> to that <a class=defnlink href="#glossary_Page_cache">page-cache</a>.</span></p>

933

934

<p>

935

See section <cite><a href="#hlr_memory" title="Caching and Memory Management Requirements">2.2.1</a></cite> for a description of and requirements

936

specifying how the value of the cache-size parameter affects the

937

operation of a <a class=defnlink href="#glossary_Page_cache">page-cache</a>. <span class=todo>Check this reference is

938

relevant after it is written. Refer to a specific requirement if possible

939

too.</span>

940

941

<p class=req id=H50154><span>The B-Tree module shall provide an interface allowing the application to set

942

the safety-level of a <a class=defnlink href="#glossary_Page_cache">page-cache</a> to one of "off", "normal" or "full",

943

given an open <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> to that <a class=defnlink href="#glossary_Page_cache">page-cache</a>.</span></p>

944

<p class=req id=H50155><span>The default value assigned to the safety-level configuration parameter of a

945

<a class=defnlink href="#glossary_Page_cache">page-cache</a> shall be "full".</span></p>

946

947

948

Description of what the safety-level actually does. Or pointer to where a

949

description and requirements can be found (transactions section?).

950

951

952

Interface to set the codec function (encryption).

953

954

955

The busy-handler. Where exactly does this come in? Transactions and

956

savepoints section?

957

958

<p>

959

The six <a class=defnlink href="#glossary_Page_cache">page-cache</a> operational parameters listed above may also be

960

queried. The following requirements specify the required query

961

interfaces.

962

963

<p class=req id=H50132><span>The B-Tree module shall provide an interface to query the current locking-mode

964

of a <a class=defnlink href="#glossary_Page_cache">page-cache</a>, given an open <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> to that <a class=defnlink href="#glossary_Page_cache">page-cache</a>.</span></p>

965

<p class=req id=H50133><span>The B-Tree module shall provide an interface to query the current journal-mode

966

967

<p class=req id=H50134><span>The B-Tree module shall provide an interface to query the current journal file

968

size-limit of a <a class=defnlink href="#glossary_Page_cache">page-cache</a>, given an open <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> to that

969

<a class=defnlink href="#glossary_Page_cache">page-cache</a>.</span></p>

970

<p class=req id=H50135><span>The B-Tree module shall provide an interface to query the current database file

971

size-limit of a <a class=defnlink href="#glossary_Page_cache">page-cache</a>, given an open <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> to that

972

<a class=defnlink href="#glossary_Page_cache">page-cache</a>.</span></p>

973

<p class=req id=H50136><span>The B-Tree module shall provide an interface to query the current cache-size

974

975

<p class=req id=H50137><span>The B-Tree module shall provide an interface to query the current safety-level

976

977

978

<p>

979

It is also possible to interrogate a b-tree database handle to determine

980

if it was opened on a temporary or <a class=defnlink href="#glossary_Persistent_database">persistent database</a>. An b-tree

981

database handle opened on a <a class=defnlink href="#glossary_Persistent_database">persistent database</a> may be queried for the

982

name of (full-path to) either the database or journal file associated

983

with the open database.

984

985

<p class=req id=H50131><span>The B-Tree module shall provide an interface to query an open b-tree database

986

handle to determine if the underlying database is a <a class=defnlink href="#glossary_Persistent_database">persistent database</a> or a

987

<a class=defnlink href="#glossary_Temporary_database">temporary database</a>.</span></p>

988

<p class=req id=H50129><span>The B-Tree module shall provide an interface allowing the application to query

989

a <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> open on a <a class=defnlink href="#glossary_Persistent_database">persistent database</a> for the name of the

990

underlying database file within the file-system.</span></p>

991

<p class=req id=H50130><span>The B-Tree module shall provide an interface allowing the application to query

992

993

underlying journal file within the file-system.</span></p>

994

995

<h3 id="section_2_1_7">2.1.7 Multi-User Database Requirements</h3>

996

997

998

<p class=req id=H50156><span>The b-tree module shall provide an interface allowing database clients to

999

acquire advisory read (shared) or write (exclusive) locks on a specific b-tree

1000

structure within the database.</span></p>

1001

1002

<ul>

1003

<li> Lock on schema memory object.

1004

<li> Locks on b-tree tables.

1005

<li> "Unlock notify" feature.

1006

<li> Mutexes/thread-safety features.

1007

</ul>

1008

1009

1010

The b-tree module preventing deadlock (by always grabbing mutexes in

1011

order of BtShared pointer) should be required here.

1012

1013

<h3 id="section_2_1_8">2.1.8 Backup/Vacuum API Requirements</h3>

1014

1015

<ul>

1016

<li> Callbacks for backup module.

1017

<li> Page read/write APIs for backup module.

1018

</ul>

1019

1020

<h3 id="section_2_1_9">2.1.9 Integrity Check Requirements</h3>

1021

1022

<ul>

1023

<li> Callbacks for backup module.

1024

<li> Page read/write APIs for backup module.

1025

</ul>

1026

1027

<h2 id="section_2_2">2.2 Other Requirements and Constraints</h2>

1028

1029

1030

<h3 id="hlr_memory">2.2.1 Caching and Memory Management Requirements</h3>

1031

1032

<ul>

1033

<li> Memory allocation related features (pcache, scratch memory, other...).

1034

<li> Default pcache implementation (sqlite3_release_memory()).

1035

<li> Schema memory object allocation (destructor registration).

1036

</ul>

1037

1038

<h3 id="section_2_2_2">2.2.2 Exception Handling Requirements</h3>

1039

1040

1041

<p>

1042

System failure. Do not corrupt the database image.

1043

<p>

1044

Three kinds of exception:

1045

<ul>

1046

<li> IO Error.

1047

<li> Malloc request failure.

1048

<li> Database image corruption.

1049

</ul>

1050

1051

<h3 id="section_2_2_3">2.2.3 Well-Formedness Requirements</h3>

1052

1053

<ul>

1054

<li> Identify the subset of file-format well-formedness requirements that

1055

this module is responsible for implementing.

1056

<li> Define how the module should respond to corrupt database files: don't

1057

crash, return SQLITE_CORRUPT as early as is practical. Should it also

1058

put the b-tree into a permanent error state?

1059

</ul>

1060

1061

1062

1063

1064

<h1 id="section_3">3 Module API</h1>

1065

1066

1067

1068

Description of the interface in btree.h. Also other interfaces accessed by

1069

external modules. Including release_memory() and those pager interfaces that

1070

are accessed directly by other modules. All of these requirements will be

1071

descended/derived from requirements in the previous sections. Some of the

1072

text could/should be pulled in from btree.h.

1073

1074

1075

The name of sqlite3BtreeBeginStmt() should probably change to

1076

sqlite3BtreeOpenSavepoint(). Matches the pager layer and is a more

1077

accurate description of the function.

1078

1079

1080

There are only a few places in which the pager object is used directly,

1081

always to call some trivial get/set configuration function. These should

1082

be replaced somehow with sqlite3BtreeXXX() APIs. Also, the current

1083

approach is probably Ok, but worth looking it over for thread-safety

1084

issues.

1085

1086

1087

It would be easier to write up if the dependency between the B-Tree

1088

layer and the sqlite3 structure did not exist. At present, it is used for:

1089

1090

<br> * The unlock-notify feature (arguments to sqlite3ConnectionBlocked() are database handles),

1091

<br> * Accessing the SQLITE_ReadUncommitted flag,

1092

<br> * Invoking the busy-handler callback,

1093

<br> * During sqlite3BtreeOpen(), to find the VFS to use,

1094

<br> * Accessing the SQLITE_SharedCache flag (for setting it),

1095

<br> * To check the same B-Tree is not attached more than once in <a class=defnlink href="#glossary_Shared-cache_mode">shared-cache mode</a>,

1096

<br> * To link the B-Tree into the pointer-order list of shared-cache b-trees used by the same handle (used for mutexes).

1097

<br> * To determine if an in-memory sub-journal should be used.

1098

<br> * To know how many savepoints are open in BtreeBeginTrans().

1099

<br> * Many, many times to assert() that the db mutex is held when the b-tree layer is accessed..

1100

1101

1102

<h2 id="section_3_1">3.1 Opening and Closing Connections</h2>

1103

1104

1105

<p>

1106

This section describes the API offered by the B-Tree module to other

1107

SQLite sub-systems to open and close <a class=defnlink href="#glossary_B-Tree_Database_Connection">B-Tree database connections</a>.

1108

1109

<pre class=api>typedef struct Btree Btree;</pre>

1110

1111

<p>

1112

A <a class=defnlink href="#glossary_B-Tree_Database_Connection">B-Tree database connection</a> is accessed by other SQLite sub-systems

1113

using an opaque handle, modelled in C code using the type "Btree*".

1114

1115

<h3 id="section_3_1_1">3.1.1 sqlite3BtreeOpen</h3>

1116

1117

1118

<pre class=api>int sqlite3BtreeOpen(

1119

sqlite3_vfs *pVfs, /* VFS to use with this b-tree */

1120

const char *zFilename, /* Name of database file to open */

1121

sqlite3 *db, /* Associated database connection */

1122

Btree **ppBtree, /* Return open Btree* here */

1123

int flags, /* Flags */

1124

int vfsFlags /* Flags passed through to VFS open */

1125

);</pre>

1126

1127

<p class=req id=H51001><span>If successful, a call to the sqlite3BtreeOpen function shall return SQLITE_OK

1128

and set the value of *ppBtree to contain a new <a class=defnlink href="#glossary_B-Tree_Database_Connection">B-Tree database connection</a>

1129

handle.</span> (P: <a class=reqlink href=#H50010>H50010</a>)</p>

1130

<p class=req id=H51002><span>If unsuccessful, a call to the sqlite3BtreeOpen function shall return an <a class=defnlink href="#glossary_SQLite_Error_Code">SQLite

1131

error code</a> other than SQLITE_OK indicating the reason for the failure. The

1132

value of *ppBtree shall not be modified in this case.</span></p>

1133

1134

<p class=req id=H51003><span>If the zFilename parameter to a call to sqlite3BtreeOpen is NULL or a pointer

1135

to a buffer of which the first byte is a nul (0x00), then sqlite3BtreeOpen

1136

shall attempt to open a connection to a <a class=defnlink href="#glossary_Temporary_database">temporary database</a>.</span></p>

1137

<p class=req id=H51004><span>If the zFilename parameter to a call to sqlite3BtreeOpen is a pointer to a

1138

buffer containing a nul-terminated UTF-8 encoded string, sqlite3BtreeOpen shall

1139

attempt to open a connection to a <a class=defnlink href="#glossary_Persistent_database">persistent database</a>.</span></p>

1140

1141

<p>

1142

The combination of the above two requirements implies that if the

1143

zFilename argument passed to sqlite3BtreeOpen is other than a NULL

1144

pointer or a pointer to a nul-terminated string, the type of or

1145

filename of the database that sqlite3BtreeOpen attempts to open a

1146

connection to are undefined.

1147

1148

<p>

1149

Valid values for the <i>flags</i> argument to the sqlite3BtreeOpen

1150

function consist of the bitwise OR of zero or more of the following

1151

symbols.

1152

1153

<pre class=api>#define BTREE_OMIT_JOURNAL 1 /* Do not create or use a rollback journal */

1154

</pre>

1155

1156

<p class=req id=H51005><span>If the BTREE_OMIT_JOURNAL bit is set in the flags parameter passed to a

1157

successful call to sqlite3BtreeOpen to open a <a class=defnlink href="#glossary_Temporary_database">temporary database</a>, then the

1158

<a class=defnlink href="#glossary_Page_cache">page-cache</a> created as a result shall not open or use a journal file for any

1159

purpose.</span></p>

1160

1161

<p>

1162

When opening a connection to a <a class=defnlink href="#glossary_Persistent_database">persistent database</a>, the value of the

1163

BTREE_OMIT_JOURNAL bit in the flags parameter is ignored by

1164

sqlite3BtreeOpen.

1165

1166

<p class=req id=H51006><span>If the BTREE_NO_READLOCK bit is set in the flags parameter passed to a

1167

successful call to sqlite3BtreeOpen to open a <a class=defnlink href="#glossary_Persistent_database">persistent database</a> and a

1168

new <a class=defnlink href="#glossary_Page_cache">page-cache</a> is created as a result of the call, then the new <a class=defnlink href="#glossary_Page_cache">page-cache</a>

1169

shall only lock the database file-system representation when writing to

1170

it.</span></p>

1171

1172

<p>

1173

When opening a connection to a <a class=defnlink href="#glossary_Temporary_database">temporary database</a>, the value of the

1174

BTREE_NO_READLOCK bit in the flags parameter is ignored, as <a class=defnlink href="#glossary_Temporary_database">temporary

1175

databases</a> are never locked for either reading or writing

1176

(<span class=todo>reference to some requirement for this statement.</span>).

1177

Whether or not a new <a class=defnlink href="#glossary_Page_cache">page-cache</a> is created when a connection to a

1178

<a class=defnlink href="#glossary_Persistent_database">persistent database</a> is opened is governed by requirements <a class=reqlink href=#H50040>H50040</a> and

1179

<a class=reqlink href=#H50050>H50050</a>.

1180

1181

<p class=req id=H51007><span>If the sqlite3BtreeOpen function is called to open a connection to a <a class=defnlink href="#glossary_Persistent_database">persistent

1182

database</a>, and the call causes a new <a class=defnlink href="#glossary_Page_cache">page-cache</a> to be created, when opening the

1183

database file using the VFS interface xOpen method the 4th parameter passed to

1184

xOpen (flags) shall be a copy of the vfsFlags value passed to sqlite3BtreeOpen.</span></p>

1185

<p class=req id=H51008><span>If the sqlite3BtreeOpen function is called to open a connection to a <a class=defnlink href="#glossary_Temporary_database">temporary

1186

database</a>, if and when a temporary file is opened to use as secondary storage

1187

using the VFS interface xOpen method the 4th parameter passed to xOpen (flags)

1188

shall be a copy of the vfsFlags value passed to sqlite3BtreeOpen with the

1189

SQLITE_OPEN_READWRITE, SQLITE_OPEN_CREATE, SQLITE_OPEN_EXCLUSIVE and

1190

SQLITE_OPEN_DELETEONCLOSE bits also set.</span></p>

1191

1192

1193

Requirements explaining how the db parameter to sqlite3BtreeOpen is used. Must be there for something.

1194

1195

<h3 id="section_3_1_2">3.1.2 sqlite3BtreeClose</h3>

1196

1197

1198

<pre class=api>int sqlite3BtreeClose(Btree*);</pre>

1199

1200

<p class=req id=H51009><span>A call to the sqlite3BtreeClose function with a valid <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database

1201

connection</a> handle passed as the only argument shall invalidate the handle,

1202

close the <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> and release all associated resources.</span></p>

1203

1204

<p>

1205

If a call to sqlite3BtreeClose is made with a value that is not a valid

1206

<a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> handle passed as the only argument, the

1207

results are undefined.

1208

1209

<p class=req id=H51010><span>If a call to sqlite3BtreeClose is made to close a <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a>

1210

while there exist open <a class=defnlink href="#glossary_B-Tree_Cursor">B-Tree cursors</a> that were opened using the specified

1211

<a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a>, they shall be closed automatically from within

1212

sqlite3BtreeClose, just as if their handles were passed to

1213

sqlite3BtreeCloseCursor.</span></p>

1214

1215

<p>

1216

See also requirement <a class=reqlink href=#H50070>H50070</a>.

1217

1218

1219

<h2 id="section_3_2">3.2 Database Image Configuration</h2>

1220

1221

1222

1223

This category doesn't work all that well. These APIs are used for other

1224

things too (i.e. switching to incremental-vacuum mode).

1225

1226

<pre class=api>#define BTREE_AUTOVACUUM_NONE 0 /* Do not do auto-vacuum */

1227

#define BTREE_AUTOVACUUM_FULL 1 /* Do full auto-vacuum */

1228

#define BTREE_AUTOVACUUM_INCR 2 /* Incremental vacuum */</pre>

1229

<pre class=api>int sqlite3BtreeSetAutoVacuum(Btree *, int);

1230

int sqlite3BtreeSetPageSize(Btree *p, int nPagesize, int nReserve, int eFix);</pre>

1231

1232

<p>

1233

Queries:

1234

1235

<pre class=api>int sqlite3BtreeGetPageSize(Btree*);</pre>

1236

<pre class=api>int sqlite3BtreeGetReserve(Btree*);</pre>

1237

<pre class=api>int sqlite3BtreeGetAutoVacuum(Btree *);</pre>

1238

1239

<h2 id="section_3_3">3.3 Connection Configuration</h2>

1240

1241

1242

<pre class=api>int sqlite3BtreeSetCacheSize(Btree*,int);

1243

int sqlite3BtreeSetSafetyLevel(Btree*,int,int,int);

1244

int sqlite3BtreeMaxPageCount(Btree*,int);</pre>

1245

1246

<p>

1247

And functions to query the current configuration:

1248

1249

<pre class=api>int sqlite3BtreeSyncDisabled(Btree*);</pre>

1250

1251

<h2 id="section_3_4">3.4 Query Interfaces</h2>

1252

1253

1254

<pre class=api>const char *sqlite3BtreeGetFilename(Btree *);</pre>

1255

1256

<p class=req id=H51011><span>A call to the sqlite3BtreeGetFilename function with a valid <a class=defnlink href="#glossary_B-Tree_Database_Connection">B-Tree database

1257

connection</a> handle opened on a <a class=defnlink href="#glossary_Persistent_database">persistent database</a> as the first argument shall

1258

return a pointer to a buffer containing the full-path of the database file

1259

formatted as a nul-terminated, UTF-8 string.</span></p>

1260

<p class=req id=H51012><span>A call to the sqlite3BtreeGetFilename function with a valid <a class=defnlink href="#glossary_B-Tree_Database_Connection">B-Tree database

1261

connection</a> handle opened on a <a class=defnlink href="#glossary_Temporary_database">temporary database</a> as the first argument shall

1262

return a pointer to a buffer to a nul-terminated string zero bytes in length

1263

(i.e. the first byte of the buffer shall be 0x00).</span></p>

1264

1265

<pre class=api>const char *sqlite3BtreeGetJournalname(Btree *);</pre>

1266

1267

<p class=req id=H51013><span>A call to the sqlite3BtreeGetJournalname function with a valid <a class=defnlink href="#glossary_B-Tree_Database_Connection">B-Tree database

1268

connection</a> handle opened on a <a class=defnlink href="#glossary_Persistent_database">persistent database</a> as the first argument shall

1269

return a pointer to a buffer containing the full-path of the journal file

1270

formatted as a nul-terminated, UTF-8 string.</span></p>

1271

<p class=req id=H51014><span>A call to the sqlite3BtreeGetJournalname function with a valid <a class=defnlink href="#glossary_B-Tree_Database_Connection">B-Tree database

1272

connection</a> handle opened on a <a class=defnlink href="#glossary_Temporary_database">temporary database</a> as the first argument shall

1273

return a pointer to a buffer to a nul-terminated string zero bytes in length

1274

(i.e. the first byte of the buffer shall be 0x00).</span></p>

1275

1276

<p>

1277

Requirement <a class=reqlink href=#H51013>H51013</a> holds true even if the <a class=defnlink href="#glossary_B-Tree_Database_Connection">B-Tree database connection</a> is

1278

configured to use an in-memory journal file or no journal file at all

1279

(<span class=todo>ref requirements</span>). In these cases the buffer returned

1280

contains the full-path of the journal file that would be used if the

1281

connection were configured to use a journal file.

1282

1283

<h2 id="section_3_5">3.5 Mutex Functions</h2>

1284

1285

1286

1287

</pre>

1288

1289

<pre class=api>void sqlite3BtreeEnter(Btree*);

1290

void sqlite3BtreeEnterAll(sqlite3*);

1291

void sqlite3BtreeLeave(Btree*);

1292

void sqlite3BtreeEnterCursor(BtCursor*);

1293

void sqlite3BtreeLeaveCursor(BtCursor*);

1294

void sqlite3BtreeLeaveAll(sqlite3*);

1295

1296

1297

</pre>

1298

1299

<h2 id="section_3_6">3.6 Transaction and Savepoint API</h2>

1300

1301

1302

<pre class=api>int sqlite3BtreeBeginTrans(Btree*,int);

1303

int sqlite3BtreeCommitPhaseOne(Btree*, const char *zMaster);

1304

int sqlite3BtreeCommitPhaseTwo(Btree*, int);

1305

int sqlite3BtreeCommit(Btree*);

1306

int sqlite3BtreeRollback(Btree*,int);</pre>

1307

1308

<pre class=api>int sqlite3BtreeBeginStmt(Btree*,int);

1309

int sqlite3BtreeSavepoint(Btree *, int, int);</pre>

1310

1311

<pre class=api>int sqlite3BtreeIsInTrans(Btree*);

1312

int sqlite3BtreeIsInReadTrans(Btree*);

1313

int sqlite3BtreeIsInBackup(Btree*);</pre>

1314

1315

1316

<h2 id="section_3_7">3.7 Reading and Traversing the Database Image</h2>

1317

1318

1319

1320

sqlite3BtreeMoveto is never called from outside of the b-tree layer. It

1321

could/should be removed from the API.

1322

1323

1324

The "bias" argument to sqlite3BtreeMovetoUnpacked is only ever true

1325

when it is called from within sqlite3BtreeInsert. This argument could/should

1326

also be removed from the API, if only to make it simpler to describe.

1327

1328

<pre class=api>typedef struct BtCursor BtCursor;</pre>

1329

1330

<pre class=api>int sqlite3BtreeCursor(

1331

Btree*, /* BTree containing table to open */

1332

int iTable, /* Index of root page */

1333

int wrFlag, /* 1 for writing. 0 for read-only */

1334

struct KeyInfo*, /* First argument to compare function */

1335

BtCursor *pCursor /* Space to write cursor structure */

1336

);

1337

int sqlite3BtreeCursorSize(void);</pre>

1338

<pre class=api>int sqlite3BtreeCloseCursor(BtCursor*);

1339

void sqlite3BtreeClearCursor(BtCursor *);</pre>

1340

1341

<pre class=api>int sqlite3BtreeFirst(BtCursor*, int *pRes);

1342

int sqlite3BtreeLast(BtCursor*, int *pRes);

1343

int sqlite3BtreeNext(BtCursor*, int *pRes);

1344

int sqlite3BtreePrevious(BtCursor*, int *pRes);

1345

int sqlite3BtreeEof(BtCursor*);</pre>

1346

1347

<pre class=api>int sqlite3BtreeKeySize(BtCursor*, i64 *pSize);

1348

int sqlite3BtreeKey(BtCursor*, u32 offset, u32 amt, void*);

1349

const void *sqlite3BtreeKeyFetch(BtCursor*, int *pAmt);

1350

const void *sqlite3BtreeDataFetch(BtCursor*, int *pAmt);

1351

int sqlite3BtreeDataSize(BtCursor*, u32 *pSize);

1352

int sqlite3BtreeData(BtCursor*, u32 offset, u32 amt, void*);</pre>

1353

1354

<pre class=api>int sqlite3BtreeCount(BtCursor *, i64 *);</pre>

1355

1356

<h3 id="section_3_7_1">3.7.1 sqlite3BtreeMovetoUnpacked</h3>

1357

1358

1359

<p>

1360

The sqlite3BtreeMovetoUnpacked function is used to

1361

1362

<pre class=api>int sqlite3BtreeMovetoUnpacked(

1363

BtCursor*,

1364

UnpackedRecord *pUnKey,

1365

i64 intKey,

1366

int bias,

1367

int *pRes

1368

);</pre>

1369

1370

<p>

1371

The following requirements specify exactly how a <a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a> is to be moved

1372

by a successful call to sqlite3BtreeMovetoUnpacked.

1373

1374

<p class=req id=L50008><span>If a call is made to sqlite3BtreeMovetoUnpacked specifying a key value for

1375

which there exists an entry with a matching key value in the b-tree structure,

1376

the <a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a> shall be moved to point to this entry. In this case *pRes

1377

(the value of the "int" variable pointed to by the pointer passed as the

1378

fifth parameter to sqlite3BtreeMovetoUnpacked) shall be set to 0 before

1379

returning.</span></p>

1380

<p class=req id=L50009><span>If a call is made to sqlite3BtreeMovetoUnpacked specifying a key value for

1381

which there does not exist an entry with a matching key value in the b-tree

1382

structure, the <a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a> shall be moved to point to an entry located

1383

on the leaf page that would contain the requested entry, were it present.</span></p>

1384

<p class=req id=L50010><span>If the condition specified in <a class=reqlink href=#L50009>L50009</a> is met and the b-tree structure

1385

contains one or more entries (is not empty), the <a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a> shall be left

1386

pointing to an entry that would lie adjacent (immediately before or after in

1387

order by key) to the requested entry on the leaf page, were it present.</span></p>

1388

<p class=req id=L50011><span>If the condition specified in <a class=reqlink href=#L50009>L50009</a> is met and the <a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a> is left

1389

pointing to an entry with a smaller key than that requested, or the cursor

1390

is left pointing a no entry at all because the b-tree structure is completely

1391

empty, *pRes (the value of the "int" variable pointed to by the pointer passed

1392

as the fifth parameter to sqlite3BtreeMovetoUnpacked) shall be set to -1.

1393

Otherwise, if the <a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a> is left pointing to an entry with a larger key

1394

than that requested, *pRes shall be set to 1.</span></p>

1395

1396

1397

1398

Not clear how to deal with these. Define an external module to

1399

encapsulate these and define sorting order etc.? That's tricky as things are

1400

because the UnpackedRecord.flags field defines the "search mode" used

1401

by sqlite3BtreeMovetoUnpacked.

1402

1403

<pre class=api>typedef struct KeyInfo KeyInfo;

1404

struct KeyInfo {

1405

sqlite3 *db; /* The database connection */

1406

u8 enc; /* Text encoding - one of the SQLITE_UTF* values */

1407

u16 nField; /* Number of entries in aColl}; hd_resolve_one {}; hd_puts { */

1408

u8 *aSortOrder; /* Sort order for each column. May be NULL */

1409

CollSeq *aColl}; hd_resolve_one {1}; hd_puts {; /* Collating sequence for each term of the key */

1410

};</pre>

1411

<pre class=api>typedef struct UnpackedRecord UnpackedRecord;

1412

struct UnpackedRecord {

1413

KeyInfo *pKeyInfo; /* Collation and sort-order information */

1414

u16 nField; /* Number of entries in apMem}; hd_resolve_one {}; hd_puts { */

1415

u8 flags; /* Boolean settings. UNPACKED_... below */

1416

i64 rowid; /* Used by UNPACKED_PREFIX_SEARCH */

1417

Mem *aMem; /* Values */

1418

};</pre>

1419

1420

<h3 id="section_3_7_2">3.7.2 sqlite3BtreeGetMeta</h3>

1421

1422

1423

<p>

1424

The sqlite3BtreeGetMeta interface may be used to retrieve the current

1425

value of certain fields from the database image header.

1426

1427

<pre class=api>void sqlite3BtreeGetMeta(Btree *pBtree, int idx, u32 *pValue);</pre>

1428

1429

<p class=req id=H51015><span>If the first parameter is a <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> handle with an open

1430

read-only or read-write transaction, and the second parameter is an integer

1431

between 0 and 7 inclusive, and the database image consists of zero pages,

1432

a call to the sqlite3BtreeGetMeta function shall set the value of *pValue to

1433

zero.</span> (P: <a class=reqlink href=#H50109>H50109</a>)</p>

1434

<p class=req id=H51016><span>If the first parameter is a <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> handle with an open

1435

read-only or read-write transaction, and the second parameter is an integer

1436

between 0 and 7 inclusive, and the database image consists of one or more

1437

pages, a call to the sqlite3BtreeGetMeta function shall set the value of

1438

*pValue to the current value of the specified 32-bit unsigned integer in the

1439

database image database header.</span> (P: <a class=reqlink href=#H50109>H50109</a>)</p>

1440

1441

<p>

1442

The two requirements above imply that if sqlite3BtreeGetMeta is called with

1443

anything other than a <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> handle with an open read-only

1444

or read-write transaction as the first argument, or with anything other than

1445

an integer between 0 and 7 (inclusive) as the second, the results are undefined.

1446

1447

<pre class=api>#define BTREE_FREE_PAGE_COUNT 0

1448

#define BTREE_SCHEMA_VERSION 1

1449

#define BTREE_FILE_FORMAT 2

1450

#define BTREE_DEFAULT_CACHE_SIZE 3

1451

#define BTREE_LARGEST_ROOT_PAGE 4

1452

#define BTREE_TEXT_ENCODING 5

1453

#define BTREE_USER_VERSION 6

1454

#define BTREE_INCR_VACUUM 7</pre>

1455

1456

<p class=req id=H51017><span>The database header field read from the database image by a call to

1457

sqlite3BtreeGetMeta in the situation specified by <a class=reqlink href=#H51016>H51016</a> shall be the 32-bit

1458

unsigned integer header field stored at byte offset (36 + 4 * idx) of the

1459

database header, where idx is the value of the second parameter passed to

1460

sqlite3BtreeGetMeta.</span> (P: <a class=reqlink href=#H50109>H50109</a>)</p>

1461

1462

1463

1464

1465

<h2 id="section_3_8">3.8 Modifying the Database Image</h2>

1466

1467

1468

<h3 id="sqlite3BtreeCreateTable">3.8.1 sqlite3BtreeCreateTable</h3>

1469

1470

<pre class=api>int sqlite3BtreeCreateTable(Btree*, int*, int flags);</pre>

1471

<pre class=api>** Every SQLite table must have either BTREE_INTKEY or BTREE_BLOBKEY set.

1472

1473

</pre>

1474

1475

<h3 id="sqlite3BtreeDropTable">3.8.2 sqlite3BtreeDropTable</h3>

1476

1477

<pre class=api>int sqlite3BtreeDropTable(Btree*, int, int*);</pre>

1478

1479

<h3 id="sqlite3BtreeClearTable">3.8.3 sqlite3BtreeClearTable</h3>

1480

1481

<pre class=api>int sqlite3BtreeClearTable(Btree*, int, int*);</pre>

1482

1483

<h3 id="sqlite3BtreeCursorHasMoved">3.8.4 sqlite3BtreeCursorHasMoved</h3>

1484

1485

<pre class=api>int sqlite3BtreeCursorHasMoved(BtCursor*, int*);</pre>

1486

1487

<h3 id="sqlite3BtreePutData">3.8.5 sqlite3BtreePutData</h3>

1488

1489

<pre class=api>int sqlite3BtreePutData(BtCursor*, u32 offset, u32 amt, void*);</pre>

1490

1491

<h3 id="sqlite3BtreeUpdateMeta">3.8.6 sqlite3BtreeUpdateMeta</h3>

1492

1493

<pre class=api>int sqlite3BtreeUpdateMeta(Btree*, int idx, u32 value);</pre>

1494

1495

<h3 id="sqlite3BtreeDelete">3.8.7 sqlite3BtreeDelete</h3>

1496

1497

1498

<pre class=api>int sqlite3BtreeDelete(BtCursor*);</pre>

1499

1500

<p class=req id=L50013><span>A successful call to the sqlite3BtreeDelete function made with a read/write

1501

<a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a> passed as the first argument shall remove the entry pointed to by

1502

the <a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a> from the b-tree structure.</span> (P: <a class=reqlink href=#H50127>H50127</a>)</p>

1503

1504

1505

Effect of a delete operation on other cursors that are pointing to the

1506

deleted b-tree entry.

1507

1508

1509

Malloc and IO error handling. Same as for sqlite3BtreeInsert.

1510

1511

<h3 id="section_3_8_8">3.8.8 sqlite3BtreeInsert</h3>

1512

1513

1514

<pre class=api>int sqlite3BtreeInsert(BtCursor*, const void *pKey, i64 nKey,

1515

const void *pData, int nData,

1516

int nZero, int bias, int seekResult);</pre>

1517

1518

<p class=req id=L50001><span>A successful call to the sqlite3BtreeInsert function made with a read/write

1519

<a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a> passed as the first argument shall insert a new entry into

1520

the b-tree structure the <a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a> is open on.</span> (P: <a class=reqlink href=#H50128>H50128</a>)</p>

1521

1522

<p>

1523

The requirement above implies that the results of passing anything else as

1524

the first argument to sqlite3BtreeInsert, for example a read-only <a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a>,

1525

are undefined.

1526

1527

<p class=req id=L50012><span>If a call to sqlite3BtreeInsert is made to insert an entry specifying a key

1528

value for which there already exists a matching key within the b-tree

1529

structure, the entry with the matching key shall be removed from the b-tree

1530

structure before the new entry is inserted.</span> (P: <a class=reqlink href=#H50128>H50128</a>)</p>

1531

1532

<p>

1533

In other words, the sqlite3BtreeInsert API could easily be renamed

1534

sqlite3BtreeInsertOrReplace. <span class=todo>We will probably need a module

1535

requirement for the "replace" operation.</span>

1536

1537

<p class=req id=L50002><span>If the <a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a> passed to sqlite3BtreeInsert as the first argument is

1538

open on a table b-tree, then the values passed as the second parameter (pKey)

1539

shall be ignored. The value passed as the third parameter (nKey) shall be

1540

used as the integer key for the new entry.</span> (P: <a class=reqlink href=#H50128>H50128</a>)</p>

1541

<p class=req id=L50003><span>If the <a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a> passed to sqlite3BtreeInsert as the first argument is

1542

open on a table b-tree, then the database record associated with the new entry

1543

shall consist of a copy of the first nData bytes of the buffer pointed to by pData

1544

followed by nZero zero (0x00) bytes, where pData, nData and nZero are the

1545

fourth, fifth and sixth parameters passed to sqlite3BtreeInsert, respectively.</span> (P: <a class=reqlink href=#H50128>H50128</a>)</p>

1546

<p class=req id=L50004><span>If the <a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a> passed to sqlite3BtreeInsert as the first argument is

1547

open on an index b-tree, then the values passed as the fourth, fifth and sixth

1548

parameters shall be ignored. The key (a database record) used by the new entry

1549

shall consist of the first nKey bytes of the buffer pointed to by pKey, where

1550

pKey and nKey are the second and third parameters passed to sqlite3BtreeInsert,

1551

respectively.</span> (P: <a class=reqlink href=#H50128>H50128</a>)</p>

1552

1553

<p>

1554

The following requirements describe the seventh and eighth paramaters passed

1555

to the sqlite3BtreeInsert function. Both of these are used to provide extra

1556

information used by sqlite3BtreeInsert to optimize the insert operation. They

1557

may be safely ignored by alternative b-tree implementations.

1558

1559

1560

There should be some rationalization for these, eventually. Some traceability

1561

from somewhere to show how the b-tree module offering these slightly esoteric

1562

interfaces is helpful to SQLite overall.

1563

1564

<p class=req id=L50005><span>If the value passed as the seventh parameter to a call to sqlite3BtreeInsert

1565

is non-zero, sqlite3BtreeInsert shall interpret this to mean that it is likely

1566

(but not certain) that the key belonging to the new entry is larger than the

1567

largest key currently stored in the b-tree structure, and optimize accordingly.</span></p>

1568

<p class=req id=L50006><span>If the value passed as the eighth parameter to a call to sqlite3BtreeInsert

1569

is non-zero, then the B-Tree module shall interpret this to mean that the

1570

the <a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a> has already been positioned by a successful call to

1571

sqlite3BtreeMovetoUnpacked specifying the same key value as is being inserted,

1572

and that sqlite3BtreeMovetoUnpacked has set the output value required by <a class=reqlink href=#L50011>L50011</a> to

1573

this value.</span></p>

1574

1575

<p>

1576

If a non-zero value is passed as the eighth parameter to sqlite3BtreeInsert

1577

and the <a class=defnlink href="#glossary_B-Tree_Cursor">b-tree cursor</a> has not been positioned as assumed by <a class=reqlink href=#L50006>L50006</a>, the

1578

results are undefined.

1579

1580

1581

Malloc and IO error handling. Maybe these should be grouped together

1582

for a whole bunch of APIs. And hook into the above via a definition of

1583

"successful call".

1584

1585

<h3 id="sqlite3BtreeIncrVacuum">3.8.9 sqlite3BtreeIncrVacuum</h3>

1586

1587

<pre class=api>int sqlite3BtreeIncrVacuum(Btree *);</pre>

1588

1589

<h2 id="section_3_9">3.9 Advisory B-Tree Locks</h2>

1590

1591

1592

<p>

1593

This section describes the b-tree module interfaces used for acquiring

1594

and querying the advisory locks that can be placed on database image

1595

pages. The locking mechanisms described in this section are only used

1596

to arbitrate between multiple clients of the same in-memory <a class=defnlink href="#glossary_Page_cache">page-cache</a>.

1597

The locking mechanism used to control access to a file-system

1598

representation of the database when multiple in-memory <a class=defnlink href="#glossary_Page_cache">page caches</a>

1599

(possibly located in different OS processes) are open on it is

1600

described in <span class=todo>this</span>.

1601

1602

<p>

1603

As well as obtaining advisory locks explicitly using the

1604

sqlite3BtreeLockTable API (see below), a read-lock on page 1 of the

1605

database image is automatically obtained whenever a <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database

1606

connection</a> opens a read-only or read-write transaction (see

1607

<span class=todo>requirement number</span>). Note that this means

1608

that a write-lock on page 1 is effectively an exclusive lock on

1609

the entire <a class=defnlink href="#glossary_Page_cache">page-cache</a>, as it prevents any other connection from opening

1610

a transaction of any kind.

1611

1612

<h3 id="section_3_9_1">3.9.1 sqlite3BtreeLockTable</h3>

1613

1614

1615

<pre class=api>int sqlite3BtreeLockTable(Btree *pBtree, int iTab, u8 isWriteLock);</pre>

1616

1617

<p>

1618

The sqlite3BtreeLockTable API allows database clients to place

1619

advisory read or write locks on a specified page of the database

1620

image. The specified page need not exist within the database image.

1621

By convention, SQLite acquires read and write locks on the root

1622

pages of table b-trees only, but this is not required to be enforced

1623

by the b-tree module. Locks may only be obtained when a database

1624

client has an open transaction. All locks are automatically released

1625

when the open transaction is concluded.

1626

1627

<p class=req id=L50016><span>A call to sqlite3BtreeLockTable, specifying a <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> handle

1628

with an open read-only or read-write transaction as the first parameter, and

1629

zero as the third parameter, shall attempt to obtain a read-lock on the database

1630

page specified by the second parameter.</span></p>

1631

<p class=req id=L50017><span>A call to sqlite3BtreeLockTable, specifying a <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> handle

1632

with an open read-write transaction as the first parameter, and a non-zero value as

1633

the third parameter, shall attempt to obtain a write-lock on the database

1634

page specified by the second parameter.</span></p>

1635

1636

<p>

1637

The two requirements above imply that the results of calling

1638

sqlite3BtreeLockTable on a <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> handle that does

1639

not currently have an open transaction, or attempting to obtain

1640

a write-lock using a <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> handle that only has

1641

a read-only transaction open are undefined.

1642

1643

1644

<p class=req id=L50019><span>If, when attempting to obtain a read-lock as described in <a class=reqlink href=#L50016>L50016</a>, there exists

1645

another <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> connected to the same <a class=defnlink href="#glossary_Page_cache">page-cache</a> that is

1646

holding a write-lock on the same database image page, the read-lock shall not

1647

be granted and the call to sqlite3BtreeLockTable shall return SQLITE_LOCKED_SHAREDCACHE.</span></p>

1648

<p class=req id=L50020><span>If, when attempting to obtain a write-lock as described in <a class=reqlink href=#L50017>L50017</a>, there exists

1649

another <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> connected to the same <a class=defnlink href="#glossary_Page_cache">page-cache</a> that is

1650

holding a read or write-lock on the same database image page, the write-lock

1651

shall not be granted and the call to sqlite3BtreeLockTable shall return

1652

SQLITE_LOCKED_SHAREDCACHE.</span></p>

1653

1654

<p>

1655

Requirement <a class=reqlink href=#L50020>L50020</a> is overly conservative. Because a write-lock may

1656

only be requested if the <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> has an open read-write

1657

transaction (<a class=reqlink href=#L50017>L50017</a>), and at most a single <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a>

1658

may have such an open transaction at one time, it is not possible for

1659

a request for a write-lock to fail because another connection is holding

1660

a write-lock on the same b-tree database image page. It may, however,

1661

fail because another connection is holding a read-lock.

1662

1663

<p>

1664

All locks are held until the current transaction is concluded. Or, if

1665

a read-write transaction is downgraded to a read-only transaction, all

1666

currently held write-locks are changed to read-locks.

1667

1668

<p class=req id=L50018><span>When a read-only or read-write transaction is concluded, all advisory b-tree locks

1669

held by the <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> shall be relinquished.</span></p>

1670

<p class=req id=L50021><span>When a read-write transaction is downgraded to a read-only transaction, all

1671

advisory b-tree write-locks held by the <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> shall be

1672

changed to read-locks.</span></p>

1673

1674

<p class=todo> The requirement above should refer to some other

1675

requirement that defines when a read-write transaction is downgraded to

1676

a read-only transaction.

1677

1678

<p class=todo> Malloc failure?

1679

1680

<p class=todo> Read uncommitted flag. Maybe this should be handled

1681

outside of the b-tree module. Is there anything to stop connections

1682

with this flag set simply not obtaining read locks? There are assert()

1683

statements in the b-tree module that need to take this flag into account,

1684

but not actual functionality.

1685

1686

<h3 id="section_3_9_2">3.9.2 sqlite3BtreeSchemaLocked</h3>

1687

1688

<pre class=api>int sqlite3BtreeSchemaLocked(Btree *pBtree);</pre>

1689

1690

<p class=req id=L50014><span>A call to the sqlite3BtreeSchemaLocked function with a valid <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree

1691

database connection</a> as the only argument shall return SQLITE_LOCKED_SHAREDCACHE

1692

if there exists another <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree database connection</a> connected to the

1693

same <a class=defnlink href="#glossary_Page_cache">page-cache</a> that currently holds a write-lock on database image

1694

page 1.</span></p>

1695

<p class=req id=L50015><span>A call to the sqlite3BtreeSchemaLocked function with a valid <a class=defnlink href="#glossary_B-Tree_Database_Connection">b-tree

1696

database connection</a> as the only argument shall return SQLITE_OK if

1697

<a class=reqlink href=#H51017>H51017</a> does not apply.</span></p>

1698

1699

<h2 id="section_3_10">3.10 What do these do?</h2>

1700

1701

1702

1703

1704

Where do the following go?

1705

1706

<pre class=api>char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot, int, int*);

1707

struct Pager *sqlite3BtreePager(Btree*);

1708

int sqlite3BtreeCopyFile(Btree *, Btree *);</pre>

1709

1710

<pre class=api>void *sqlite3BtreeSchema(Btree *, int, void(*)(void *));

1711

int sqlite3BtreeSchemaLocked(Btree *pBtree);

1712

int sqlite3BtreeLockTable(Btree *pBtree, int iTab, u8 isWriteLock);

1713

void sqlite3BtreeTripAllCursors(Btree*, int);</pre>

1714

1715

1716

I know what the following do, but is this mechanism ever used? Or has it been superceded by other tricks in OP_NewRowid?

1717

1718

<pre class=api>void sqlite3BtreeSetCachedRowid(BtCursor*, sqlite3_int64);

1719

sqlite3_int64 sqlite3BtreeGetCachedRowid(BtCursor*);</pre>

1720

1721

1722

Should move to btreeInt.h

1723

1724

<pre class=api>typedef struct BtShared BtShared;</pre>

1725

1726

<h2 id="section_3_11">3.11 APIs not branded sqlite3BtreeXXX()</h2>

1727

1728

1729

<ul>

1730

<li> sqlite3PagerLockingMode

1731

<li> sqlite3PagerJournalMode

1732

<li> sqlite3PagerIsMemdb (vacuum and backup).

1733

<li> sqlite3PagerJournalSizeLimit

1734

<li> sqlite3PagerFile (used by sqlite3_file_control() and pragma lock_proxy_file).

1735

<li> sqlite3PagerPagecount (pragma page_count and backup).

1736

<li> Page APIs used by backup routines:

1737

<ul>

1738

<li> sqlite3PagerGet

1739

<li> sqlite3PagerWrite

1740

<li> sqlite3PagerGetData

1741

<li> sqlite3PagerGetExtra

1742

<li> sqlite3PagerUnref

1743

<li> sqlite3PagerTruncateImage

1744

<li> sqlite3PagerSync

1745

<li> sqlite3PagerFile

1746

<li> sqlite3PagerCommitPhaseOne, sqlite3PagerCommitPhaseTwo

1747

<li> sqlite3PagerBackupPtr

1748

</ul>

1749

</ul>

1750

1751

1752

<h1 id="section_4">4 Module Implementation</h1>

1753

1754

1755

<h2 id="section_4_1">4.1 Database Image Traversal</h2>

1756

1757

1758

<h2 id="section_4_2">4.2 Database Image Manipulation</h2>

1759

1760

1761

1762

This section should describe exactly how bits and bytes are shifted

1763

around when the database image is traversed and modified. i.e. how the b-tree

1764

balancing works, deleting an internal cell from an index b-tree etc.

1765

1766

<h3 id="section_4_2_1">4.2.1 Creating a B-Tree Structure</h3>

1767

1768

<h3 id="section_4_2_2">4.2.2 Clearing a B-Tree Structure</h3>

1769

1770

<h3 id="section_4_2_3">4.2.3 Deleting a B-Tree Structure</h3>

1771

1772

1773

<h3 id="section_4_2_4">4.2.4 Inserting, Replacing and Deleting B-Tree Entries</h3>

1774

1775

1776

<p>

1777

The following two sections describe the way entries are added and removed

1778

from B-Tree structures within a database image.

1779

1780

<p>

1781

As one might expect, the algorithms described in the following sections

1782

involve adding and removing b-tree cells to and from b-tree node pages.

1783

The format of b-tree node pages is described in detail in

1784

<cite><a href="#ref_file_format" title="">[1]</a></cite>. This document does not describe the exact

1785

way in which content is manipulated within a page, as these details are

1786

considered not considered high-level enough to be documented outside of

1787

the SQLite source code itself. For the purposes of the descriptions in

1788

the following sections, a b-tree node page is considered to be a container

1789

for an ordered list of b-tree cells. Cells may be inserted into or removed

1790

from any position in the ordered list as required.

1791

1792

<p>

1793

A b-tree node page has a finite capacity. If one of the algorithms

1794

described here is required to insert a cell into a b-tree node page,

1795

and there is not enough free space within the page to accommodate the

1796

cell, it is still nominally inserted into the requested position within

1797

the node, but becomes an <a class=defnlink href="#glossary_Overflow_Cell">overflow cell</a>. <a class=defnlink href="#glossary_Overflow_Cell">Overflow cells</a> never remain so

1798

for very long. If an insert, replace or delete entry operation creates

1799

one or more <a class=defnlink href="#glossary_Overflow_Cell">overflow cells</a>, the b-tree structure is rearranged so that

1800

all cells are stored within the body of a b-tree node page before the

1801

operation is considered complete. This process of rearranging the b-tree

1802

structure is termed b-tree balancing, and is described in section

1803

<cite><a href="#btree_balancing_algorithm" title="B-Tree Balancing Algorithm">4.2.5</a></cite>.

1804

1805

1806

<h4 id="section_4_2_4_1">4.2.4.1 B-Tree Insert/Replace Entry</h4>

1807

1808

1809

<p>

1810

This section describes the way in which new entries may be inserted

1811

into a b-tree structure, and how existing entries may be replaced. Both

1812

of these operations are accessed using the sqlite3BtreeInsert API.

1813

1814

<p>

1815

An insert/replace operation involves the following steps:

1816

1817

<ol>

1818

<li> Based on the supplied key and value, and the type of b-tree being

1819

inserted into, allocate and populate any required overflow pages.

1820

<span class=todo>Should reference file-format requirements that

1821

provide the formula for doing this.</span>

1822

1823

<li> Attempt to move the b-tree write cursor to an entry with a key

1824

that matches the new key being inserted. If a matching entry is

1825

found, then the operation is a replace. Otherwise, if the key is

1826

not found, an insert.

1827

1828

1829

<li> Requirements <a class=reqlink href=#L50008>L50008</a>, <a class=reqlink href=#L50009>L50009</a>, <a class=reqlink href=#L50010>L50010</a> and <a class=reqlink href=#L50011>L50011</a> apply to the cursor

1830

seek operation here. This ensures that if the search does not find

1831

an exact match, the cursor is left pointing to the leaf page that

1832

the new entry should be added into.

1833

1834

<li> As specified by <a class=reqlink href=#L50006>L50006</a>, the cursor may already be positioned. In

1835

this case the seek operation is not required.

1836

</ol>

1837

1838

<li> If a matching key was found in the b-tree, then it must be removed and

1839

the new entry added in its place.

1840

1841

1842

<li> If there are one or more overflow pages associated with the entry

1843

being replaced, they are moved to the free-list.

1844

<li> The cell corresponding to the entry being removed is removed from

1845

the b-tree node page.

1846

<li> The new cell is inserted in the position previously occupied by the

1847

cell removed in the previous step. If the page is not a leaf page,

1848

then the first four-bytes (the child-page pointer) of the old

1849

cell are copied to the first four bytes of the new cell. If the new

1850

cell is larger than the cell that it replaced, then it may become

1851

an <a class=defnlink href="#glossary_Overflow_Cell">overflow cell</a>.

1852

</ol>

1853

1854

<li> If no matching key was found in the b-tree, then the new cell is inserted

1855

into the leaf page that the cursor was left pointing to by step 1. The

1856

new cell may become an <a class=defnlink href="#glossary_Overflow_Cell">overflow cell</a>.

1857

1858

<li> If the new cell is now an <a class=defnlink href="#glossary_Overflow_Cell">overflow cell</a>, then the balancing algorithm

1859

(see section <cite><a href="#btree_balancing_algorithm" title="B-Tree Balancing Algorithm">4.2.5</a></cite>) is run on the

1860

overflowing b-tree node page.

1861

</ol>

1862

1863

<h4 id="section_4_2_4_2">4.2.4.2 B-Tree Delete Entry</h4>

1864

1865

1866

<p>

1867

This section describes the way in which entries may be removed from

1868

a b-tree structure, as required when the sqlite3BtreeDelete (section

1869

<cite><a href="#sqlite3BtreeDelete" title="sqlite3BtreeDelete">3.8.7</a></cite>) API is invoked. Removing an entry

1870

from a b-tree table involves the following steps:

1871

1872

<ol>

1873

<li> All overflow pages in the overflow page chain (if any) associated

1874

with the entry must be moved to the database free-list. If the

1875

database image is an autovacuum database, the pointer-map entries

1876

that correspond to each overflow page in the chain must be updated.

1877

1878

<li> The b-tree cell corresponding to the entry must be removed from

1879

the b-tree structure.

1880

</ol>

1881

1882

1883

Note about the optimization that makes it possible to move overflow pages

1884

to the free-list without reading their contents (i.e. without loading them

1885

into the cache).

1886

1887

<p>

1888

If the b-tree entry being removed is located on a leaf page (as is always the

1889

case with table b-tree structures), then deleting an entry from a b-tree

1890

is quite simple.

1891

1892

1893

1894

1895

1896

<p><i>Figure 2 - Delete from an Internal Node</i>

1897

</center>

1898

1899

1900

<h3 id="btree_balancing_algorithm">4.2.5 B-Tree Balancing Algorithm</h3>

1901

1902

1903

<ul>

1904

<li><p>The <b>balance deeper</b> sub-algorithm is used when the root page of

1905

a b-tree is overfull. It creates a new page and copies the

1906

entire contents of the overfull root page to it. The root page

1907

is then zeroed and the new page installed as its only child.

1908

The balancing algorithm is then run on the new child page (in case

1909

it is overfull).

1910

1911

<li><p>The <b>balance shallower</b> sub-algorithm is used when the root page

1912

of a b-tree has only a single child page. If possible, the data from

1913

the child page is copied into the root-page and the child page discarded.

1914

1915

<li><p>The <b>balance quick</b> sub-algorithm is used in a very specific,

1916

but common scenario. It is used only for table b-trees, when a new entry that

1917

has a key value greater than all existing keys in the b-tree is inserted and

1918

causes the right-most leaf page of the b-tree structure to become overfull.

1919

1920

<li><p>The <b>balance siblings</b> sub-algorithm is run when a b-tree page that

1921

is not the root-page of its b-tree structure is either overfull or underfull.

1922

1923

1924

1925

1926

</ul>

1927

1928

<h4 id="section_4_2_5_1">4.2.5.1 Balance Deeper</h4>

1929

1930

<ol>

1931

<li> Allocate a new page (the child-page).

1932

<li> Copy page data from root-page to child-page (including <a class=defnlink href="#glossary_Overflow_Cell">overflow cells</a>).

1933

<li> Fix pointer map entries associated with new child-page content.

1934

<li> Zero the root-page.

1935

<li> Set the right-child pointer of the root-page to point to the new child-page.

1936

<li> Set the pointer map entry for the new child page.

1937

<li> Execute the balance procedure on the new child page.

1938

</ol>

1939

1940

1941

1942

1943

1944

<p><i>Figure 3 - Example Balance Deeper Transform</i>

1945

</center>

1946

1947

1948

<h4 id="section_4_2_5_2">4.2.5.2 Balance Shallower</h4>

1949

1950

1951

<ol>

1952

<li> Copy node data from child-page to root-page.

1953

<li> Fix pointer map entries associated with new root-page content.

1954

<li> Move child-page to database image free-list.

1955

</ol>

1956

1957

1958

1959

1960

1961

<p><i>Figure 4 - Example Balance Shallower Transform</i>

1962

</center>

1963

1964

1965

<h4 id="section_4_2_5_3">4.2.5.3 Balance Quick</h4>

1966

1967

1968

<ol>

1969

<li> Allocate a new page (the new sibling-page).

1970

1971

<li> Populate the new sibling page with the new b-tree entry.

1972

1973

<li> Add a new divider cell to the parent. The divider cell contains a

1974

pointer to the page that is currently the right-child of the parent.

1975

The key in the new divider cell is a copy of the largest key in the

1976

page that is currently the right-child of the parent.

1977

1978

<li> Set the right-child of the parent page to point to the new sibling page.

1979

1980

<li> If the database is an auto-vacuum database, set the pointer map

1981

entry associated with the new sibling page. If the cell on the new

1982

sibling page contains a pointer to an overflow page, set the pointer map

1983

entry associated with the overflow page.

1984

1985

<li> Execute the balance procedure on the parent page.

1986

</ol>

1987

1988

1989

1990

1991

1992

<p><i>Figure 5 - Example Balance Quick Transform</i>

1993

</center>

1994

1995

1996

<h4 id="balance_siblings">4.2.5.4 Balance Siblings</h4>

1997

1998

1999

<p class=req id=L51001><span>The <a class=defnlink href="#glossary_Balance-Siblings_Algorithm">balance-siblings algorithm</a> shall redistribute the b-tree cells currently

2000

stored on a overfull or underfull page and up to two sibling pages, adding

2001

or removing siblings as required, such that no sibling page is overfull and

2002

the minimum possible number of sibling pages is used to store the

2003

redistributed b-tree cells.</span></p>

2004

2005

2006

The following description describes how balance() is to be implemented. This

2007

represents (I think) the lowest level of detail that should be in this document.

2008

One skilled in the art could use this description to reimplement SQLite's

2009

<a class=defnlink href="#glossary_Balance-Siblings_Algorithm">balance-siblings algorithm</a>. We also need requirements at a higher level

2010

of detail in this section. Something to test!

2011

2012

<p>

2013

The <a class=defnlink href="#glossary_Balance-Siblings_Algorithm">balance-siblings algorithm</a>, as implemented by SQLite, is described as

2014

a series of steps below. <span class=todo> there are a few terms used

2015

below that need definitions/clarifications.</span>

2016

2017

<ol>

2018

<li> Determine the set of sibling pages to redistribute the cells of, using

2019

the following rules:

2020

2021

<li> If the parent page has three or fewer child pages, then all child

2022

pages are deemed to be sibling pages for the purposes of the <a class=defnlink href="#glossary_Balance-Siblings_Algorithm">balance-siblings

2023

algorithm</a>.

2024

<li> If the page being balanced is the left-most child of the parent

2025

page, then the three left-most child pages are used as the siblings.

2026

<li> If the page being balanced is the right-most child of the parent

2027

page, then the three right-most child pages are used as the siblings.

2028

<li> Otherwise, if none of the above three conditions are true, then the

2029

sibling pages are page being balanced and the child pages immediately

2030

to the left and right of it.

2031

</ol>

2032

2033

<li> Determine an ordered list of cells to redistribute. There are several

2034

variations of this step, depending on the type of page being balanced.

2035

2036

<li> If the page being balanced is a leaf page of a table b-tree,

2037

then the list of cells to redistribute is simply the concatenation

2038

of the ordered lists of cells stored on each sibling page, in order

2039

from left-most sibling to right-most.

2040

<li> If the page being balanced is a leaf page of an index b-tree, then

2041

the list of cells to redistribute is comprised of the cells on each

2042

of the sibling pages and the divider cells in the parent page that

2043

contain the pointers to each sibling page except the right-most. The

2044

list is arranged so that it contains:

2045

<ul>

2046

<li> The cells from the left-most sibling page, in order, followed by

2047

<li> the divider cell from the parent page that contains the pointer

2048

to the left-most sibling (if there is more than one sibling

2049

page), followed by

2050

<li> the divider cell that contains the pointer to the second left-most

2051

sibling and the cells from the remaining sibling page (if there are three

2052

sibling pages).

2053

</ul>

2054

<li> If the page being balanced is an internal b-tree node, then the list of

2055

cells to redistribute is determined as described in the previous case.

2056

However, when balancing an internal node each cell is associated with

2057

the page number of a child page of one of the sibling pages. The page

2058

number associated with cells stored on a sibling page is the same as

2059

the page number stored as the first four bytes of the cell. The page

2060

number associated with a divider cell within the parent page is the page

2061

number of the right-child page of the sibling page to which the divider

2062

cell contains a pointer.

2063

</ol>

2064

2065

<li> Determine the new cell distribution, using the following steps:

2066

2067

<li> Assign as may cells as will fit from the start of the ordered list of

2068

cells to the left-most sibling page. Then, if any cells remain, assign

2069

one to be a divider cell, and as many as will fit to the next sibling

2070

page. Repeat until all cells have been assigned a location.

2071

<span class=todo> no divider cells for table b-tree leaf balance</span>

2072

2073

<li> The previous step generates a distribution that is biased towards the

2074

left-hand side. The right-most sibling may even be completely

2075

empty (if the last cell in the ordered list was assigned to be a

2076

divider cell). To rectify this, cells are moved out of the second

2077

right-most sibling page and into the right-most, one at a time, until

2078

there is at least one cell in the right-most sibling page and to move

2079

another cell would mean that the right-most sibling page is more full

2080

than the next to right-most sibling page. This is repeated for the next

2081

right-most pair of sibling pages, shifting cells out of the third

2082

right-most sibling page and into the second right-most, and so on.

2083

<span class=todo> note about divider cells </span>

2084

</ol>

2085

2086

<li> Determine the set of database pages to use as the new sibling pages.

2087

2088

2089

<li> If there were an equal or greater number of siblings identified

2090

in step 1 than are required by the distribution calculated in step 3,

2091

reuse as many as possible, starting with the left-most. If step 3

2092

calculated a distribution that requires more sibling pages than were

2093

identified in step 1, allocate the required extra pages using the

2094

<span class=todo>Refer to ???</span> algorithm.

2095

2096

<li> Arrange the new sibling pages from left to right in ascending

2097

page number order. The new sibling page with the smallest page number

2098

becomes the left-most sibling page, and so forth.

2099

</ol>

2100

2101

<li> Populate the new sibling pages.

2102

2103

<li> Populate each new sibling page with the required set of cells. If the

2104

page being balanced is not a leaf page, then the child-page pointer

2105

field of each cell is populated with the page-number associated with

2106

the cell as part of step 2 above.

2107

2108

<li> If the page being balanced is not a leaf page, then the right-child

2109

pointer stored in the page header of each new sibling page must also

2110

be populated. For each new sibling page except the right-most, this

2111

field is set to the page number associated with the cell that

2112

immediately follows the cells stored on the page (the cell that was

2113

assigned to be divider cell in step 3). For the right-most sibling page,

2114

the right-child pointer is set to the value that was stored in the

2115

right-child pointer of the right-most original sibling page identified

2116

in step 1.

2117

</ol>

2118

<li> Populate the parent page.

2119

2120

<li> If the page being balanced is (was) not a leaf page of a table

2121

b-tree, the cells that contained pointers to the old sibling

2122

pages are replaced by the cells designated as divider cells as part

2123

of step 3. The right-child pointer field of the first divider cell

2124

is overwritten with the page number of the first new sibling page, and

2125

so on.

2126

2127

<li> If the page being balanced is (was) a leaf page of a table

2128

b-tree, the cells that contained pointers to the old sibling

2129

pages are replaced by a divider cell associated with all but the

2130

right-most sibling page. The child-page number stored in each divider

2131

cell is set to the page number of the associated sibling. The integer key

2132

value stored in each divider cell is a copy of the largest integer key

2133

value stored on the associated sibling page.

2134

2135

<li> Before balancing, the parent page contained a pointer to the right-most

2136

sibling page, either as part of a cell or as the right-child pointer

2137

stored in the page header. Either way, this value must be overwritten

2138

with the page number of the new right-most sibling page.

2139

2140

</ol>

2141

2142

<li> Populate pointer map entries.

2143

2144

<li> For each sibling page that was not also an original sibling page, the

2145

associated pointer-map entry must be updated. Similarly, the pointer-map

2146

entry associated with each original sibling page that is no longer a

2147

sibling page must be updated.

2148

<li> For each cell containing an overflow pointer that has been moved from one

2149

page to another, the pointer-map entry associated with the overflow page

2150

must be updated.

2151

<li> If the page being balanced is (was) not a leaf, then for each cell that

2152

has moved from one page to another the pointer-map entry associated with

2153

the cell's child page must be updated.

2154

<li> If the page being balanced is (was) not a leaf, then the pointer-map entry

2155

associated with each sibling's right-child page may need to be updated.

2156

</ol>

2157

</ol>

2158

2159

<h3 id="section_4_2_6">4.2.6 Page Allocation and Deallocation</h3>

2160

2161

2162

2163

Amongst other things, this section needs to explain our old pals the

2164

DontWrite() and DontRollback() optimizations.

2165

2166

<h4 id="free_overflow_chain">4.2.6.1 Moving an overflow-chain to the free-list</h4>

2167

2168

2169

2170

Describe how this can sometimes be done without reading the content of

2171

overflow pages.

2172

2173

<h3 id="section_4_2_7">4.2.7 Incremental Vacuum Step</h3>

2174

2175

2176

2177

2178

2179

<h2 id="section_4_3">4.3 Transactions and Savepoints</h2>

2180

2181

2182

2183

Requirements surrounding how transactions are made atomic and isolated.

2184

Also how savepoints are implemented. What happens to active cursors after

2185

a rollback or savepoint-rollback.

2186

2187

<h1 id="section_5">5 References</h1>

2188

2189

2190

2191

2192

SQLite Online Documentation,<u>SQLite Database File Format</u>,

2193

<a href="fileformat.html">http://www.sqlite.org/fileformat.html</a>.

2194

2195

2196

SQLite Online Documentation,<u>Application Defined <a class=defnlink href="#glossary_Page_cache">Page Cache</a></u>,

2197

<a href="c3ref/pcache_methods.html">http://www.sqlite.org/c3ref/pcache_methods.html</a>.

2198

2199

2200

SQLite Online Documentation,<u>OS Interface Object</u>,

2201

<a href="c3ref/vfs.html">http://www.sqlite.org/c3ref/vfs.html</a>.

2202

2203

2204

</table>

2205

2206

2207