• 数据库索引技术之B树索引

    前面我们介绍了 哈希索引LSM树索引 ,它们都基于日志结构式的数据文件。虽然工程界对这种索引的认可度正与日俱增,但还远不是最受欢迎的索引技术。

    那么,目前应用最广的索引技术又是什么呢?

    您可能早就有所耳闻——这就是本文要探讨的 B树b-tree )索引。B树可以说是数据库索引技术中的武林盟主,能够几十年长盛不衰,必定有它自己的独门秘诀。

    索引结构

    跟我们在 LSM树 一节中提到的 SSTable 一样,B树也是将数据组织成有序形式,因此支持范围查询。尽管如此,它们的底层结构却完全不同,B树有自己独特的设计哲学。

    阅读全文
  • 数据库索引技术之LSM树

    上次我们分享了采用哈希索引实现的存储引擎,它总是将写操作不断追加到数据文件,就跟写日志一样。这种日志结构式的存储引擎,数据记录顺序由写入时间决定,同一键的旧记录由新记录取代。

    SSTable

    由于数据在写入时,自动切分成一个个文件。数据库需要在后台对文件进行合并,以减少文件数,进而加快查询。如果待合并文件里的数据是有序的,我们就可以采用归并排序算法来提高合并效率。

    虽然这看起来会违背顺序写的原则,但也有办法解决,我们稍后介绍。

    现在,我们将数据文件格式改成这样:①文件中的所有记录,按照 key )来排序;②排序保证了每个键只在文件中出现一次,不会有重复的旧记录。姑且将这种格式叫做 排序字符串表sorted string table )简称 SSTable

    阅读全文
  • 数据库索引技术之哈希索引

    我们介绍过一个用几行 Shell 代码实现的简陋数据库,它的插入性能很好,但查询性能很差。

    我们都知道,想要提升数据库的查询速度,索引必不可少 。那么,索引的底层结构都是怎样的呢?它们又是如何工作的呢?

    实际上,数据库索引技术因底层数据结构不同,可以分为好几种:

    • 哈希索引hash index
    • LSM树log structured merge tree
    • B树b-tree

    其中,哈希索引的结构最为简单,但也很常用。今天我们就先将它一举拿下!

    哈希索引结构

    键值对存储引擎其实跟编程语言中的 字典dictionary )类型很像,而字典底层通常是用 哈希表hash table )实现的。既然哈希表可以用来索引内存中的数据,应该也可以用来索引磁盘数据吧?

    阅读全文
  • 仅用几行代码就撸了个数据库!

    最近重读《数据密集型应用系统设计》这本书,看到第三章《数据存储与检索》,主要讲数据库内部的索引技术。

    从本质上讲,数据库主要是做两件事情:

    1. 当你给它数据时,它帮你保存数据(存储);
    2. 当你查询数据时,它帮你取回数据(检索);

    这两件事情看似简单,背后却暗含玄机。那么,数据库内部到底是如何存储数据的呢?又是如何检索数据的呢?

    你可能会有这样的疑问:我作为一个开发人员,为什么需要知道数据库内部是怎么工作的呢?

    阅读全文