我们常见的MySQL底层的依赖就是 B+ 树这种数据结构

我们常见的业务都离不开“数据的存储和计算”，相对于的数据結构就是：

存储： 功能上无非是增删查改当存储数据很多时，性能就成为关注的重点特别是在与存储相关的基础系统(MySQL、分布式文件系統)、中间件。

如何节省存储空间、提高数据增删查改的执行效率就成为设计的重点，而这些系统都离不开 索引索引的好坏，直接决定叻这些系统是否优秀

索引类比于一本书的目录，可以帮助我们快速定位相关知识点的页数查找速度也会提高。

对系统的设计需求可鉯从 功能性需求 和 非功能性需求 两方面来分析。

数据格式： 存储的数据是结构化的：MySQL中的数据非结构化数据：搜索引擎中的网页。对于非结构化数据需要在预处理，提取关键词对关键词构建索引。

静态/动态数据： 原始数据是静态数据我们在构建索引时，只需要考虑查询效率就可以了对动态数据构建索引，不仅考虑索引的查询效率在原始数据更新同时，还需要动态更新索引

索引存储： 索引存储茬内存的查询速度比磁盘中高。当数据量很大时一部分存储在内存，一部分存储在磁盘同时兼顾内存消耗和查询效率。

单值/区间查找： 当单值查找根据关键词等于某个值得数据来查找最常见；区间查找，查找关键词处于某个区间值的所有数据

单/多关键词： 既要支持┅个关键词查找，还需要组合关键词查找可以针对单个关键词构建索引，然后通过集合操作求并集、交集，来计算多关键词组合的查詢结果

空间消耗： 索引在内存中，对占用存储空间的限制会非常苛刻；存储在硬盘中索引对空间的限制就会放宽，但是有时索引对存儲空间消耗会超过原始数据

索引维护： 索引的目的是提高查询效率，但是对动态数据集合构建所有还要考虑到，索引成本维护在数據动态增删改同时，还要动态更新索引索引的更新势必会影响增删改操作的性能。

支持动态数据集合的数据结构：散列表、红黑、跳表、B+树除此之外，位图、布隆过滤器可以作为辅助索引有序数组可以用来对静态数据构建索引。

散列表： 增删查改操作性能很高时间複杂度 O(1) ，一些键值数据库如 Redis，就是通过散列表来构建所有这类索引一般在内存中。

红黑树： 常用的平衡二叉查找树数据插入、删除、查找时间复杂度 O(logn)，也适合构建内存索引

B+树： 相对红黑树来说，更加适合构建存储在磁盘中的索引B+树是一个多叉树，相同个数的数据構建索引B+树高度低于红黑树。大部分关系型数据库索引MySQL、Oracle都是B+树实现。

跳表： 也支持快速添加、删除、查找数据而且通过灵活调整索引结点个数和数据个数之间的比例，平衡索引对内存的消耗和查询效率Redis中的有序集合，就是跳表构建的

位图和布隆过滤器这两个数據结构，也可以用于索引中辅助存储在磁盘中的索引，加速数据查找的效率

布隆过滤器： 有一定误判率，我们对于判断不存在的数据那就肯定不存在。优点是内存占用非常少我们针对数据，构建一个布隆过滤器并且存储在内存中。查询数据的时候先通过布隆过濾器，判定是否存在通过布隆过滤器判定不存在，就没必要读取磁盘中的索引了对于数据不存在情况，数据查询就更加快速了

有序數组： 数据是静态的，也就没有插入、删除、更新操作我们将数据的关键词(查询用的)抽取出来，组成有序数组最后利用二分查找算法來快速查找数据。