区分SQLite中的B-树和B+树——索引和存储

区分SQLite中的B-树和B+树——索引和存储

在网上看一些帖子的时候。发现有人说Sqlite中组织管理数据库文件存储的机制为B-树。

本人觉着这么说非常的不严谨。

于是本人翻出了《the definitive guide to sqlite》SECOND EDITON。经过再次查阅，想在这里总结一下。

在Sqlite中B-树和B+树的出处的却别，换句话说。就是SQLite这个嵌入式数据库中，索引机制和文件存储机制的区别。

1.索引

对索引多说几句吧，我们去砍树，可以用手把它推到，但是利用斧子可以很快的把树干倒。

检索操作（更新，删除，插入都会用到检索操作）就如砍树，索引就是我们的斧子。

首先他和好用。加快了检索速度。同时如斧子一样。不是让你白用的。斧子是买来的。就是借来的也是欠了个人情的。总之就是使用索引（斧子）去检索数据（去看书）是需要代价的。

没错，这是必须的。斧子放在家里占地方啊。索引也是占内存的啊。亲，而且如果不是内存数据库，索引还要占外存的地方呢。

斧子花钱了。除了检索操作不需要更新索引，删除，插入都要更新索引啊，亲，这就是辅助性工具的开销。

我们一定要明确一点。索引和表、数组、一个变量一样是实实在在的在我们的硬盘上或者内存中躺着的。

说的再直白一些，他就是个数据结构（其实数据结构这个词听抽象的，你觉得呢？）。总之就是，占内存，我们用程序可以直接控制他的。

他可以清清楚楚的躺在我们的面前。不要嫌我啰嗦，这些就是索引的本质。

上面说到，索引和数据结构很近。好吧。我们比较典型的索引数据结构有两大类，1：散列，其通过一个叫散列函数的东西，利用数值计算，便可很快得知目标记录所在散列表位置，然后根据散列表位置里的信息便可快速找到它了。又分静态散列和动态散列，关于他们的知识点，百度吧，谷歌吧。

2：树，随着数据量的增长，树能自己调整自己。可以容纳很多数据。利用对比来快速定位，往往对比次数与树的深度有很大关系。一般成对数级的时间复杂度。一般典型的有B数（又名B-树，不要说有那么一个树叫B减树或者B杠树），B+树，AVL树，红黑树（RBTree）。

关于他们的知识点，百度吧，谷歌吧。。

2.存储

我说的简单些吧。

内存小，外存大。数据库文件大，内存装不下，怎么办？解决方法很简单。先装一部分，先使吧。

很眼熟啊感觉。

操作系统里有木有？（动态或静态）页面管理机制有木有？缺页中断有木有？

这里有个概念“页面（pager）”。sqlite中是这么说的。一个数据库文件被连续的分割成了X个页面，并给个页面号。就是“块儿”和“块儿号”。

这点东西不熟悉的再查查相关资料吧。

3.SQLite中B树和B+树的应用。

上图是从文章开头处的书中，解出来的一段。