内容简介：如果没有索引，对于无序的数据，我们查找数据就只能依靠遍历，算法时间复杂度为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 -- 普通索引与唯一索引
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Beginning ASP.NET 4 in C# and Vb
Imar Spaanjaars / Wrox / 2010-3-19 / GBP 29.99
This book is for anyone who wants to learn how to build rich and interactive web sites that run on the Microsoft platform. With the knowledge you gain from this book, you create a great foundation to ......一起来看看 《Beginning ASP.NET 4 in C# and Vb》 这本书的介绍吧!
