数据检索的玄铁剑——索引
从搬运 DTO 到 CRUD 在如今的开发模式下，服务端程序员离原始数据越来越远，和农夫山泉一样，他们不生产数据，他们只是 DTO 的搬运工。从各种 service 中获取数据，再使用 Lambda 进行拆分组装成为了他们的日常工作。 然而，随着各家大厂都开始“降本增效”，DTO 的搬运工越来越不具备竞争力，“技多不压身”变成了下一阶段的 OKR，于是「CRUD 工程师」便“应运而生”了。 本文的内容便是围绕着 CRUD 中的 R(ead)展开的。 数据检索的玄铁剑——索引 在现实生活中，如果你想使用新华字典查询一个字，在没有背下来具体页码的情况下，第一步多半是打开目录，根据拼音首字母快速的锁定目标数据所在的位置范围。如下图 👇 索引究竟是什么？ 百度百科是从数据库的角度出发给出了一个索引的定义，维基百科也并没有为 CS 中的索引做一个概述，而是细分了多个领域来介绍 👉https://en.wikipedia.org/wiki/Index 本质上，索引是一种用于提高数据检索效率的技术，它可以是一种复杂的数据结构（Hash，B Tree……），也可以就是一个简单的下标。 为了更好的理解索引，先看一下没有索引的查询是什么样的？ 没有索引的查询 上班路上，你和一个长发姐姐擦肩而过，来到公司，惊喜的发现她竟然也在这栋楼上班，此时电梯停在了 3 楼，小姐姐出去之后你便继续乘到了 6 楼，虽然你一直写着代码，但此时你的心早已飞去了三楼。 OK，那么问题来了，如果你想再见到那个长发姐姐，第一想法是什么？一定不是发表白墙吧。 在纠结了半天之后，最后你还是选择了最原始但也是最简单的办法，去三楼的工位一个个找。 你一边遍历着所有工位上的人，一边幻想着等再见面时的场景。终于皇天不负苦心人，在你离她还有六个工位的时候，你见到了她。就在你以为终于能发出“一起喝咖啡”的邀约时，一位靓仔从你的后面“瞬移”到她面前，然后说出了那句“有时间一起喝咖啡吗？”。 事了拂尘去，靓仔最后回头看了你一眼，然后说到：“小伙子，爷有索引”。 微观视角的索引——什么才是有意义的索引 上面这个例子就是一个很典型的场景，在没有索引的情况下，查询就变得简单粗暴——全表扫描。查询耗时完全由数据量决定，海量数据的查询基本无法满足需求。 由于遍历的时间复杂度是 O(n)，那么为了让索引变得有意义，其时间复杂度必定是小于 O(n)。 常刷算法题的小伙伴们都知道，经常出现查找的两类数据结构就是数组和树，其实也对应着两种最常见的索引。 哈希索引：复杂度为 O(1) 树索引：复杂度为 O(log n) 哈希索引原理是根据属性组合直接通过哈希函数计算出结果数据的地址，一般来说更快（包括建索引的效率和查询效率），具体性能依赖于数据集和哈希函数的匹配程度。 树索引原理是基于属性组合建立树再根据二分查找定位数据，虽然建索引和查找速度都慢一些，但优势是可以支持范围查询和 front-n 属性匹配（前缀匹配）的查询。其中 front-n 属性的查询意思是，属性组合中的前 1 到前 n 个属性组成的子组合的查找。例如属性组合是 A-B-C，那么树索引可以支持 A、A-B、A-B-C 三个属性组合的查找。...