内容简介：如果没有索引，对于无序的数据，我们查找数据就只能依靠遍历，算法时间复杂度为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)。现实中的例子是常见的关系型数据库中的索引实现。
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
- MySQL索引使用说明(单列索引和多列索引)
- Elasticsearch索引的基本操作(3)-索引的滚动索引
- Coreseek 增量索引模拟实时索引
- Coreseek 增量索引模拟实时索引
- MySQL高效索引之覆盖索引
- MySQL -- 普通索引与唯一索引
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
创业的艺术2.0
〔美〕盖伊·川崎 / 刘悦、段歆玥 / 译言·东西文库／电子工业出版社 / 2016-9 / 68
“创业者导师”——盖伊•川崎的《创业的艺术2.0》被阿丽亚娜•赫芬顿评为“终极的创业手册”。无论您是企业家、小企业主、企业开拓者还是非盈利组织的领导人，都可以让你的产品、服务或理念获得成功。 盖伊选取了不用角度，探索前十年商界的巨大变化，并寻求解决之道。曾经所向披靡的市场巨头深陷水深火热之中，社交媒体也取代了人际关系和广告，成为营销推广的主要渠道。众筹也成为广大投资者的可行之举。“云”更是每......一起来看看 《创业的艺术2.0》 这本书的介绍吧!
