我们介绍过一个用几行 Shell 代码实现的简陋数据库,它的插入性能很好,但查询性能很差。
我们都知道,想要提升数据库的查询速度,索引必不可少 。那么,索引的底层结构都是怎样的呢?它们又是如何工作的呢?
实际上,数据库索引技术因底层数据结构不同,可以分为好几种:
- 哈希索引( hash index )
- LSM树( log structured merge tree )
- B树( b-tree )
其中,哈希索引的结构最为简单,但也很常用。今天我们就先将它一举拿下!
哈希索引结构
键值对存储引擎其实跟编程语言中的 字典 ( dictionary )类型很像,而字典底层通常是用 哈希表( hash table )实现的。既然哈希表可以用来索引内存中的数据,应该也可以用来索引磁盘数据吧?