福田企业网站优化排名,wordpress文章勒出,申请域名建立网站,wordpress图片集“基础不是100分考60分#xff0c;而是建摩天大楼的地基。” 为什么需要索引#xff1f;
#xff08;1#xff09;在实际的软件开发工作的本质都可以抽象为“对数据的存储和计算”。对应到数据结构和算法中#xff0c;那“存储”需要的就是数据结构#xff0c;“计算”需… “基础不是100分考60分而是建摩天大楼的地基。” 为什么需要索引
1在实际的软件开发工作的本质都可以抽象为“对数据的存储和计算”。对应到数据结构和算法中那“存储”需要的就是数据结构“计算”需要的就是算法。 2对于存储的需求功能上无外乎增删改查。当存储的数据很多性能就会成为这些系统要关注的重点特别是在存储相关的基础系统、中间件中。 3“如何节省存储空间、如何提高数据增删改查的执行效率”解决这样的问题离不开索引
索引的需求定义
对于系统设计需求一般可以从功能性需求和非功能性需求两方面来分析
1. 功能性需求
1数据是格式化数据还是非格式化数据 构建索引的原始数据可分为两类
一类是结构化数据如MySQL 中的数据一类是非结构化数据如搜索引擎中网页。非结构化数据一般需要预处理提取出查询关键词对关键词构建索引。
2数据是静态数据还是动态数据
如果是一组静态数据在构建索引时只需考虑查询效率动态数据构建索引不仅要考虑索引的查询效率在原始数据更新的同时还需要动态地更新索引
3索引存储在内存还是硬盘
当数据量小时索引可以存储在内存中。原始数据量很大时对应的索引可能也会很大。内存有限可能需要将索引存储在磁盘中。第三种情况一部分存储在内存一部分存储在磁盘这样可以兼顾内存消耗和查询效率。
4单值查找还是区间查找
所谓单值查找也就是根据查询关键词等于某个值的数据。所谓区间查找就是查找关键词处于某个区间值的所有数据。不同的应用场景查询的需求会多种多样。
5单关键词查找还是多关键词组合查找
对于单关键词的查找索引构建起来相对简单。多关键词查询要分多种情况: A像 MySQL 这种结构化数据的查询可以实现针对多个关键词的组合建立索引 B像搜索引擎这样的非结构数据的查询可以针对单个关键词构建索引然后通过集合操作如求并集、求交集等计算出多个关键词组合的查询结果。 不同的场景不同的原始数据对于索引的需求也会千差万别
2. 非功能性需求
1不管是存储在内存中还是磁盘中索引对存储空间的消耗不能过大。
如果存储在内存中索引对占用存储空间的限制就会非常苛刻如果存储在硬盘中也不能掉以轻心因为有时索引对存储空间的消耗会超过原始数据
2在考虑索引查询效率的同时还要考虑索引的维护成本。
基于动态数据集合构建的索引要考虑索引的维护成本。因为在原始数据动态增删改的同时也需要动态的更新索引。而索引的更新势必会影响到增删改操作的性能。
构建索引常用的数据结构有哪些
如散列表、红黑树、跳表、B 树除此之外位图、布隆过滤器可以作为辅助索引有序数组可以用来对静态数据构建索引 散列表增删改查操作的时间复杂度是 O(1)被一些键值数据库用来构建索引如 Redis、Memcache。这类索引一般都构建在内存中。 红黑树是常用的平衡二叉查找树数据插入、删除、查找的时间复杂度是 O(logn)也非常适合用来构建内存索引。Ext 文件系统中对磁盘块的索引用的就是红黑树。 B 树比起红黑树更加适合构建存储在磁盘中的索引 1B 树是一个多叉树对相同个数的数据构建索引B 树的高度要低于红黑树。 2当借助索引查询数据时读取 B 树索引需要的磁盘 IO 次数会更少。 所以如 MySQL、Oracle等大部分关系型数据库的索引都是用 B 树来实现的 跳表也支持快速添加、删除、查找数据通过调整索引结点个数和数据个数之间的比例可以很好地平衡索引对内存的消耗及其查询效率。Redis 中的有序集合就是用跳表来构建的 布隆过滤器有一定的判错率但可以规避它的短处发挥它的长处 1尽管对于判定存在的数据可能并不存在但是对于判定不存在的数据是一定不存在 2布隆过滤器有个大特点内存占用非常少所以可以针对数据构建一个布隆过滤器存储在内存中。 3查询数据时如果布隆过滤器判定数据不存在就不必读取磁盘中的索引了。对于数据不存在的情况数据查询就更加快速了。 有序数组也可以被作为索引如果数据是静态的只有查询操作可以把数据的关键词查询用的抽取出来组织成有序数组然后利用二分查找算法来快速查找数据。
笔记整理来源 王争 数据结构与算法之美
