认识达内从这里开始

索引是大多数软件编程开发程序员在学习与开发数据库的时候都需要熟练掌握并应用的一个编程技术，而本文我们就通过案例分析来简单了解一下，索引应用场景分享。

索引的原理是拿额外的存储空间换取查询时间，增加了写入数据的开销，但使读取数据的时间复杂度一般从O(n)降低到O(logn)甚至O(1)。索引不仅在数据库中广泛使用，前后端的开发中也在不知不觉运用。

在数据集比较大时，不用索引就像从一本没有目录而且内容乱序的新华字典查一个字，得一页一页全翻一遍才能找到;用索引之后，就像用拼音先在目录中先找到要查到字在哪一页，直接翻过去就行了。书籍的目录是的树状结构，那么软件世界常见的索引有哪些数据结构，分别在什么场景使用呢?

哈希表(HashTable)：哈希表的原理可以类比银行办业务取号，给每个人一个号(计算出的Hash值)，叫某个号直接对应了某个人，索引效率是高的O(1)，消耗的存储空间也相对更大。K-V存储组件以及各种编程语言提供的Map/Dict等数据结构，多数底层实现是用的哈希表。

二叉搜索树(BinarySearchTree)：有序存储的二叉树结构，在编程语言中广泛使用的红黑树;属于二叉搜索树，确切的说是"不完全平衡的"二叉搜索树。从C++、Java的TreeSet、TreeMap，到Linux的CPU调度，都能看到红黑树的影子。Java的HashMap在发现某个Hash槽的链表长度大于8时也会将链表升级为红黑树，而相比于红黑树"更加平衡"的AVL树反而实际用的更少。

平衡多路搜索树(B-Tree)：这里的B指的是Balance而不是Binary，二叉树在大量数据场景会导致查找深度很深，解决办法就是变成多叉树，MongoDB的索引用的就是B-Tree。

叶节点相连的平衡多路搜索树(B+Tree)：B+Tree是B-Tree的变体，只有叶子节点存数据，叶子与相邻叶子相连，MySQL的索引用的就是B+树，Linux的一些文件系统也使用的B+树索引inode。其实B+树还有一种在枝桠上再加链表的变体：B*树，暂时没想到实际应用。

日志结构合并树(LSMTree)：LogStructuredMergeTree，简单理解就是像日志一样顺序写下去，多层多块的结构，上层写满压缩合并到下层。LSMTree其实本身是为了优化写性能牺牲读性能的数据结构，并不能算是索引，但在大数据存储和一些NoSQL数据库中用的很广泛，因此这里也列进去了。

字典树(TrieTree)：又叫前缀树，从树根串到树叶就是数据本身，因此树根到枝桠就是前缀，枝桠下面的所有数据都是匹配该前缀的。这种结构能非常方便的做前缀查找或词频统计，的应用有：自动补全、URL路由。其变体基数树(RadixTree)在Nginx的Geo模块处理子网掩码前缀用了;Redis的Stream、Cluster等功能的实现也用到了基数树(Redis中叫Rax)。

跳表(SkipList)：是一种多层结构的有序链表，插入一个值时有一定概率"晋升"到上层形成间接的索引。跳表更适合大量并发写的场景，不存在红黑树的再平衡问题，Redis强大的ZSet底层数据结构就是哈希加跳表。

倒排索引(Invertedindex)：这样翻译不太直观，可以叫"关键词索引"，比如书籍末页列出的术语表就是倒排索引，标识出了每个术语出现在哪些页，这样我们要查某个术语在哪用的，从术语表一查，翻到所在的页数即可。倒排索引在全文索引存储中经常用到，比如ElasticSearch非常核心的机制就是倒排索引;Prometheus的时序数据库按标签查询也是在用倒排索引。

数据库主键之争：自增长vsUUID。主键是很多数据库非常重要的索引，尤其是MySQL这样的RDBMS会经常面临这个难题：是用自增长的ID还是随机的UUID做主键?

自增长ID的性能高，但不好做分库分表后的全局ID，自增长的规律可能泄露业务信息;而UUID不具有可读性且太占存储空间。争执的结果就是找一个兼具二者的优点的折衷方案：用雪花算法生成分布式环境全局的ID作为业务表主键，性能尚可、不那么占存储、又能保证全局单调递增，但引入了额外的复杂性，再次体现了取舍之道。

再回到数据库中的索引，建索引要注意哪些点呢?

定义好主键并尽量使用主键，多数数据库中，主键是效率高的聚簇索引;

在Where或GroupBy、OrderBy、JoinOn条件中用到的字段也要按需建索引或联合索引，MySQL中搭配explain命令可以查询DML是否利用了索引;

类似枚举值这样重复度太高的字段不适合建索引(如果有位图索引可以建)，频繁更新的列不太适合建索引;

单列索引可以根据实际查询的字段升级为联合索引，通过部分冗余达到索引覆盖，以避免回表的开销;

尽量减少索引冗余，比如建A、B、C三个字段的联合索引，Where条件查询A、AandB、AandBandC都可以利用该联合索引，就无需再给A单独建索引了;

根据数据库特有的索引特性选择适合的方案，比如像MongoDB，还可以建自动删除数据的TTL索引、不索引空值的稀疏索引、地理位置信息的Geo索引等等。

【免责声明】本文系本网编辑部分转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!请读者仅作参考。更多内容请加抖音太原达内IT培训学习了解。