数据库索引

  1. 1. 为什么需要索引
  2. 2. 功能性需求
  3. 3. 非功能性需求
  4. 4. 构建索引常用的数据结构

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

1. 为什么需要索引

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

2. 功能性需求

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

3. 非功能性需求

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

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

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

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

文章标题:数据库索引

文章字数:605

本文作者:Leilei Chen

发布时间:2021-07-10, 21:56:10

最后更新:2021-07-10, 21:56:48

原始链接:https://www.llchen60.com/%E6%95%B0%E6%8D%AE%E5%BA%93%E7%B4%A2%E5%BC%95/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏