SQLite是如何工作的？第2部分：Btree

SQLite数据库被组织成固定大小的页面。我做了一个有1k页的示例数据库。

有两种页面：内部页面和叶子页面，数据只存储在叶子页面中。

我上一次提到，每次我读一页时，我都会输入一些打印语句来告诉我，就像这样：

sqlite&>SELECT*FROM FUN WHERE id=10；读取btree页，页码4122读取btree页，页码900读取btree页，页码5。

让我们更多地了解一下这些Btree是如何工作的！首先是一些理论。

通常，当我考虑跟踪树访问时，我会考虑“需要跳转到新节点的次数”。因此，在深度为10的二进制树中，您可能需要最多跳10次。

数据库优化中最重要的事情之一是磁盘I/O。读取比您绝对需要读取的数据更多的数据是非常昂贵的，因为在文件中查找新位置需要很长时间。与将数据读入内存相比，搜索数据所需的CPU时间要少得多(请参阅：计算机很快！，每个程序员都应该知道的延迟数字)。

因此，对于简单的数据库扫描，读取超出需要的数据是一个巨大的问题

我们希望尽可能少地读取数据库以写入查询，并且。

我的文件系统的“块大小”是4k，这意味着一次读取少于4k是不可能的。

由此我们可以得出结论，我们希望阅读尽可能少的页面。Btree的组织方式是每个节点都有很多子节点，以保持较小的深度，这样我们就不必读取太多页面来查找一行。

我的100,000行SQLite数据库有一个深度为3的btree，所以要获取阳极，我只需要读取3页。如果我使用二叉树，我需要做LOG(100000)/LOG(2)=16次查找！这是这个数字的五倍多。所以这些btree看起来是个不错的主意。

到目前为止，我们一直在谈论，好像只有一棵Btree一样。这根本不是真的！我的数据库有一个表和两个btree。

每个表都有一个由内部节点和叶节点组成的btree。叶子节点包含所有数据，内部节点指向其他子节点。

该表的每个索引也有自己的btree，您可以在其中查找列值对应的行id。这就是维护大量索引的速度很慢的原因--每次插入一行时，您需要更新的树数量与您拥有的索引数量一样多。

让我们更深入地研究一个查询。原来SQLite对每个btree的每一页都进行二进制搜索，以找出下一步要转到哪个节点。我已经打印出它在进行二进制搜索时尝试的索引。

sqlite>；SELECT*FROM FUN WHERE id=1000；读取Btree页，页号1Searching for 1000.读取Btree页，页号4122页中的单元格数量：62idx：30idx：14idx：6idx：2idx：2idx：0读取Btree页，页号900页中的单元格数量：67idx：33idx：16idx：7idx：3idx：1idx：2读取Btree页，页码7页码：69idx：34idx：16idx：7idx：3idx：1idx：2-查找键：99001读取一个btree页，页码2页中的单元格数：19当前键：索引9，值51627当前键：索引14，值75920Curr。值97372当前键：索引50，值98277当前键：索引58，值98698当前键：索引62，值98927当前键：索引64，值99044当前键：索引63，值98985读取btree页，页码4129页中的单元格数量：59Current Key：索引29，值99015当前键：索引14，值99000当前键：索引21，值99007。

哇，那可是一大堆工作啊。实际上这里有两个不同的搜索，在两个不同的树上。

在索引BTREE-99001中查找与数字1,000相关的行ID。(一些行ID文档)。

看到它在每页内对99001进行二进制搜索，真的很漂亮！在索引btree中查找1000时，我不太明白如何让它打印出它正在做的比较，因为它做了一些奇怪的函数指针魔术来进行比较。

Kamal现在正在用我旁边的Python构造模块解析SQLite数据库，它是AMAZING。可能会有未来的分期付款。谁知道呢！