关于自己实现索引

人类一思考,上帝就发笑。可怕的未知,但是还是想探寻什么。

如果有一个超过4g左右的文本文件,内容大概是keytvalue的格式,如何查找某一个key对应的value。问题的起源就在这里。曾经自以为聪明的认为,这个问题的正解是,load到数据库,建立索引,使用sql查询。直到自己发问,数据库是如何实现索引,索引在硬盘中是如何存储的,如果索引超过了内存的大小,那如何来使用这个索引。从数据库到各种大数据平台,就算没有索引,也提供了使用主键查询,又是如何实现的呢。

因为索引是对数据或者地址的引用,索引的前提是否是可以根据地址定位到数据?如果不可以定位到数据,那索引又该如何实现和使用呢?

目前假想的索引实现是:
1 保存在内存或者文件系统中。如果在文件系统中,索引需要便于查找的文件格式,比如,使用btree实现的索引,每个treeNode使用256字节,整个文件的大小除以256就是索引的行数,root节点在文件头部,根据树查找需要的key的位置。
2 从位置中得到数据的首地址,调用文件系统api读取此地址加上数据长度的内容,结果就是需要的value。
3 索引的生成如果是在文件系统中,则会有大量的io,生成过程会比较慢。

要印证这些到自我实现,需要经历什么样的过程呢。数据结构只听过名字,还是得从数据结构入手吧。

什么是btree,这个结构的插入,删除,更新又是如何处理的呢?从这里开始吧。