优化学校网站建设方案,镜像网站做排名,精品网站建设价格,推荐网站建设的电销该怎么打文章目录1. 为什么需要索引2. 索引的需求定义2.1 功能性需求2.2 非功能性需求3. 构建索引常用的数据结构4. 总结索引这种常用的技术解决思路#xff0c;底层往往会依赖哪些数据结构#xff1f;
1. 为什么需要索引
实际的软件开发中#xff0c;它们的本质都可以抽象为“对数…
文章目录1. 为什么需要索引2. 索引的需求定义2.1 功能性需求2.2 非功能性需求3. 构建索引常用的数据结构4. 总结索引这种常用的技术解决思路底层往往会依赖哪些数据结构
1. 为什么需要索引
实际的软件开发中它们的本质都可以抽象为“对数据的存储和计算”。
存储增删改查。一旦存储的数据很多性能就成了关注的重点“如何节省存储空间、提高数据增删改查的效率”是设计的重点。不夸张地说索引设计得好坏直接决定了这些系统是否优秀。
2. 索引的需求定义
2.1 功能性需求 数据是格式化数据还是非格式化数据要构建索引的原始数据类型有很多。分为两类一类是结构化数据比如MySQL数据另一类是非结构化数据比如网页。对于非结构化数据需要做预处理提取出查询关键词对关键词构建索引。 数据是静态还是动态如果原始数据是静态数据不会有数据的增加、删除、更新操作所以在构建索引的时候只需要考虑查询效率就可以了。大部分情况下我们都是对动态数据构建索引不仅要考虑到索引的查询效率还需要动态更新索引。 索引存储在内存还是硬盘存储在内存查询速度比磁盘高。索引大的时候内存有限可能不得不将索引存在磁盘中。还可以一部分存在内存一部分存在磁盘兼顾内存消耗和查询效率。 单值查找还是区间查找 单关键词查找还是多关键词组合查找比如搜索引擎中构建的索引既要支持一个关键词的查找比如“数据结构”也要支持组合关键词查找比如“数据结构 算法”。对于多关键词查询来说要分多种情况。像MySQL这种结构化数据的查询需求可以实现针对多个关键词的组合建立索引对于像搜索引擎这样的非结构数据的查询需求可以针对单个关键词构建索引然后通过集合操作比如求并集、求交集等计算出多个关键词组合的查询结果。
2.2 非功能性需求 不管是存在内存中还是磁盘中索引对存储空间的消耗不能过大。 考虑索引查询效率的同时还要考虑索引的维护成本。索引的目的是提高查询效率但是基于动态数据集合构建的索引还要考虑索引的维护成本。因为在原始数据动态增删改的同时也需要动态的更新索引。而索引的更新会影响到增删改操作的性能。
3. 构建索引常用的数据结构
常用来构建索引的数据结构就是讲过的几种支持动态数据集合的数据结构。比如散列表、红黑树、跳表、B树。除此之外位图、布隆过滤器可以作为辅助索引有序数组可以用来对静态数据构建索引。 散列表增删改查操作的性能非常好时间复杂度是O1。一些键值数据库比如Redis、Memcache就是使用散列表来构建索引的。这类索引一般都构建在内存中。 红黑树作为一种常用的平衡二叉查找树数据插入、删除、查找的时间复杂度是Olog n也非常适合用来构建内存索引。Ext文件系统中对磁盘块的索引用的就是红黑树。 B树比红黑树来说更适合构建存储在磁盘中的索引。B树是多叉树对相同个数的数据构建索引B树的高度要低于红黑树。查询时读取B树索引需要的磁盘IO次数更少。所以大部分关系型数据库索引比如MySQL、Oracle都是用B树来实现的。 跳表也支持快速添加、删除、查找数据。而且通过灵活调整索引结点个数和数据个数之间的比例可以很好地平衡索引对内存的消耗及其查询效率。Redis中的有序集合就是用跳表来构建的。 布隆过滤器有一定的判错率。尽管对于判定存在的数据有可能并不存在但是对于判定不存在的数据那肯定就不存在。更大的特点就是内存占用非常少。针对数据构建一个布隆过滤器存储在内存中。要查询时先通过布隆过滤器判定是否存在。如果判定数据不存在就没必要读取磁盘中的索引了。对于数据不存在的情况数据查询就更加快速了。 有序数组也可被作为索引。如果数据是静态的可以把数据的关键词抽取出来组织成有序数组然后利用二分查找来快速查找数据。
4. 总结
架构设计离不开数据结构和算法。要想成长为一个优秀的业务架构师、基础架构师数据结构和算法的根基一定要打稳。那些看似很惊艳的架构设计思路实际上都是来自最常用的数据结构和算法。
