常见的索引方式

栏目: 编程工具 · 发布时间: 6年前

内容简介:如果没有索引,对于无序的数据,我们查找数据就只能依靠遍历,算法时间复杂度为O(N);对于有序的数据,可以使用二分查找, 时间复杂度为O(lgN),但是此处的有序还有一个要求,就是数据是空间连续的,即如果是使用链表保存,即便是有序也无法使用 二分查找。现实世界中,数据的出现总是无序的,对于无序的数据,常有这么几个数据结构来构建索引:

如果没有索引,对于无序的数据,我们查找数据就只能依靠遍历,算法时间复杂度为O(N);对于有序的数据,可以使用二分查找, 时间复杂度为O(lgN),但是此处的有序还有一个要求,就是数据是空间连续的,即如果是使用链表保存,即便是有序也无法使用 二分查找。

现实世界中,数据的出现总是无序的,对于无序的数据,常有这么几个数据结构来构建索引:

  • Hash table: https://en.wikipedia.org/wiki/Hash_table 哈希表,教科书上有,太经典了,不说了。其优点是查找速度非常快,缺点是无序,因此无法借助哈希表进行范围查找。现实 中的例子是:Redis中的KV。

  • LSM Tree: https://en.wikipedia.org/wiki/Log-structured_merge-tree 对于机械硬盘来说,随机读写非常耗时,但是顺序读写非常的快。LSM Tree就特别适合处理这种情况。首先,在内存中会维护一个 表(比如哈希表,或者跳跃表)来实现KV,每次写入之前,都会先追加到硬盘上的一个Append Only的日志文件。然后周期性的合并 老的Append Only的文件。Append Only的日志文件每达到一定大小之后,就写入到一个新的文件,老的文件会进行合并&排序。此后 查找起来就很快了,先从内存中的数据查找,没找到就从日志文件里从新到旧查找,因为文件都是有序的,所以可以使用二分查找。

  • B-Tree: https://en.wikipedia.org/wiki/B-tree B-Tree,通过控制树的高度,当节点保存的数据很多时,每下降一层,就可以过滤掉很多数据。当保证节点所保存的数据是有序的 这个特性时,B-Tree就可以进行范围查找了。查找时间复杂度为O(lgN)。现实中的例子是常见的关系型数据库中的索引实现。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

iOS软件开发揭密

iOS软件开发揭密

虞斌 / 电子工业出版社 / 2011-5-1 / 79.00元

本书以严密的体系性提供了iPhone和iPad软件开发从入门到专家的系统性知识,并提供来源于真实项目的可重用商业代码。书中的每个实例都是项目经验的提炼,深入浅出地讲解iPhone和iPad软件开发的核心技术要点,基本涵盖了iOS软件开发在真实商业项目中所需要的所有主题,并将实例介绍的技术深度和超值的实用性结合在一起,成为本书的特色。 随书附赠的光盘中包含了书中大量案例的完整工程源代码,可以让......一起来看看 《iOS软件开发揭密》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

在线进制转换器
在线进制转换器

各进制数互转换器

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具