关于B-tree多种定义的分析

Posted on by
2

最近我在学习B-tree的过程中遇到了不同文献有不同定义的问题。经过一段时间的思考与调研，我总结了一些自己的想法，于是就有了写作本文的打算。本文将简单介绍索引与B-tree的关系，并试图简要分析历史上B-tree不同定义的本质原因。

开胃菜

做数据库的同学对B-tree一定不会感到陌生。B-tree（中文翻译为B树或者B-树）是我们熟知的一个经典数据结构，它是一种平衡的多路查找树，广泛应用于计算机文件系统与数据库索引。B-tree的前身最早可以追溯到J. E. Hopcroft于1970年提出的2-3 tree，而它正式登上历史舞台则要归功于R. Bayer和E. McCreight在1972年发表的论文"Organization and Maintenace of Large Ordered Indexes"。

说到B-tree与数据库系统的关联，就不得不提到索引。索引(Index)是数据库系统中的一个重要概念，本质上说，索引是一种为了帮助数据库系统高效获取数据而由其维护着的满足特定查找算法的数据结构。索引的类型有很多种，如B-tree索引，R-tree索引，Full-Text索引，Hash索引等，当然本文仅仅关注与讨论B-tree索引。一般来说，实际应用中由于数据库系统维护的数据库文件可能体积非常庞大，对应的索引也就很大，不可能一次读入主存。因此索引会以索引文件的形式存放在磁盘上。传统磁盘I/O速度相对于主存要慢上若干个数量级（目前情况是5个），所以涉及磁盘的查找我们必须想办法减少磁盘I/O的次数。

而B-tree就是能够达到这样一种效果的数据结构。我们知道B-tree与一般的平衡树如AVL-Tree，Red-Black Tree的一个显著区别是B-tree的每个内结点可以拥有很多个Children（这个度量被称为内结点出度，下文会更深入的讨论之），那么我们可以在技术上使B-tree的结点大小为磁盘一个页的大小，并且在新建结点时直接申请一个页大小的空间，使得结点的物理存储位置也是在一个页里，这样就能实现存取一个结点只需一次磁盘I/O。在最坏情况下，B-tree的一次检索最多需要H（树的高度）次的磁盘I/O，记N为B-tree中的Key的数据量，t为内结点出度的1/2，我们可以证明H ≤ logt(N+1)/2，亦即渐进复杂度为O(H)=O(logtN)。这意味着，一棵拥有200万Key的B-tree，在内结点出度为200时它的树高H最多为3。实际上，为了取得更大的内结点出度，各个数据库一般会采用B-tree的变种如B+-tree，B*-tree来实现索引，比如MySQL的存储引擎InnoDB就采用B+-tree来实现聚簇索引。
Continue reading →

MySQL Temporary Table探究

Posted on by
4

Ⅰ. 问题的引入
让我们先来观察几条非常简单的MySQL语句：

create temporary table tmp(id int, data char(20));

Query OK, 0 rows affected (0.00 sec)

create table tmp(id int, data char(20));

Query OK, 0 rows affected (0.00 sec)

drop table tmp;

Query OK, 0 rows affected (0.00 sec)

drop table tmp;

Query OK, 0 rows affected (0.00 sec)

drop table tmp;

ERROR 1051 (42S02): Unknown table 'tmp'

这是丁奇师兄提出的引导性的问题，几条语句看似简单，不过接下来我们提出的一连串问题与进行的研究可都是围绕它们来的！
对于以上语句，你很容易会产生类似于以下的疑问：
1. 上述语句在一个session中先后创建了两个名为tmp的table，只不过一个是temporary table，一个是normal table。问题来了：temporary table为何可以与同名的normal table共存？
2. 上述语句成功执行了两条DROP TABLE语句，那么每一条语句操作的对象是哪个table呢？亦即同名的temporary table与normal table之间的优先级关系是如何的？
很好，有了问题就知道了前进的方向！接下来我们就从这两个问题入手，由浅及深，开始我们的探索之旅吧！

Continue reading →

Hello world!

Posted on by
9

Welcome to WordPress. This is your first post. Edit or delete it, then start blogging!

以上内容是我安装WordPress后自动生成的，看着亲切，不忍删除；既然题目是Hello world!，那么顺便贴上K&R的经典hello, world代码，以示开篇之意：

#include <stdio.h>

main()
{
	printf("hello, world\n");
}

拥有了自己的域名并开博，自然是一件非常开心的事，WordPress的开源特性又让我拥有对blog的完全控制权，能按照自己的意愿定制站点，很棒。

Continue reading →