好玩的网站列表

索引的实现，底层一般会依赖于哪些数据结构？

1. 为什么需要索引

• 为了能够尽快得到想要的数据 — 提高性能
• 选取高效的数据结构，在针对访问特性有比较好的访问速度的同时，减少空间上的占用
  • 如何节省存储空间
  • 如何提高数据增删改查的执行效率

2. 功能性需求

• 格式化数据还是非格式化数据？
  • 结构化数据
    • 比如MySQL数据
  • 非结构化数据
    • 比如搜索引擎当中的网页
    • 一般需要进行预处理，提取出查询关键词，对关键词建立索引
• 静态数据还是动态数据？
  • 静态数据
    • 意味着没有增删改查
    • 只需要考虑查询效率即可
  • 动态数据
    • 当原始数据更新的同时，我们还需要动态的更新索引
• 索引存储在内存还是硬盘？
  • 存储在内存
    • 访问速度快
    • 原始数据量大的前提下，对应的索引也会非常大
    • 因为内存有限，我们将不得不存放到内存当中
  • 存储在硬盘
  • 部分存储在内存，部分在硬盘
• 单值查找还是区间查找
  • 单值查找
    • 查询关键词等于某个值的数据
  • 区间查找
    • 查找关键词处于某个区间值的数据
• 单关键词还是多关键词组合的查找
  • 多关键词查询
    • 对于结构化数据的，
      • 实现针对多个关键词的组合建立索引
    • 对于非结构化数据的
      • 建立针对单个关键词的索引
      • 然后通过集合操作，计算出查询结果

3. 非功能性需求

• 无论存放在内存还是磁盘当中，对于存储空间的消耗不能过大
• 在考虑索引查询效率的同时，还要考虑索引的维护成本

4. 构建索引常用的数据结构

• 散列表
  • 构建内存索引
  • 如Redis Memcache
• 红黑树
  • 构建内存索引
  • Ext文件系统中对磁盘块的索引
• B+树
  • 比起红黑树，更适合在磁盘当中构建索引
  • 多叉树，比起红黑树，高度更低，IO更少
  • 大部分关系型数据库的索引，会使用B+树来实现
    • MySQL
    • Oracle
• 跳表
  • Redis中的有序集合

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 stone2paul@gmail.com