《IT 核心手册》:一册在手,核心技术全拥有
《IT 核心手册》由北京海纳技术咨询有限公司联合海外华人技术社区共同推出的计算机
核心技术专业期刊。出版内容是当今世界最先进的计算机科学技术和创新理论,旨在引进
国际先进科学技术,为国人所用。
《IT 核心手册》为永久免费下载期刊,反映最先进的国际核心科学技术,提供免费答疑
服务。
官方网址:http://www.distributed-cluster.com。
如果您觉得我们的服务对您有帮助,请推荐给您的朋友们,让更多的人学到核心技术。
揭开数据库内核的神秘面纱系列(二)
海纳咨询 王怀志
散列文件属于一种非常常用的文件,无论在国产数据库当中,还是国外成熟的商业数据库,这
个算法可以说是杀手锏级别的。因为它的应用实在太普遍了,几乎所有的凡是叫数据库的都有类
似的算法,可能有的叫法不一样而以。
生成散列桶文件根定长文件类似,就是算法不同罢了。一个文件记录就可以看成一个桶,每个
桶一般能容纳 n 个“逻辑记录”,这个“逻辑记录”就是数据库中常说的记录。根据每个逻辑记
录的 key 值,直接用文件指针定位到文件的某一位置。当发生溢出时,在文件尾在继续开辟空间
存储,然后将这个新的位置保存到 hash 桶的后面的溢出位,其实就是文件指针的那个文件位置
id。然后,所有的该 hash 值得溢出被排成一个逻辑链表了。
当前绝大多数数据库厂商都将 hash 文件系统放进了数据库内核当中。 本来 hash 一般是内存当
中的数据结构体,通过某种散列算法较快的定位某个元素,hash 算法目前还不能直接定位,只
是比树结构平均定位效率要快些。由于以前的数据库文件都是 B+树,查找操作所耗费的 io 次数
比较多, 性能较慢, 于是数据库内核研发人员决定将 hash 的思想引入到文件里, 在 80 年代以后,
操作系统对底层磁盘的柱面,扇区的封装,对外提供了文件 api 函数,实现 hash 文件变得轻而
易举了。当前世界上的绝大部分数据库都采取了直接调用 api 的方法, 有个别数据库则采取针对
硬件的磁盘块定位。
一,直接 hash 文件算法
文件例子:(最前一列的数字为说明性数字,不是文件里面的数据,后三列为文件中的数据)
定长文件结构定义:
typedef struct _NODE
{
int id;
char sex[2];