数据存储在磁盘或内存中时，我们需要高效的数据结构来访问和获取数据。本文将介绍 8 种常用的数据库索引结构，并讨论它们的优点和缺点。

B 树

B 树是一种流行的基于磁盘的索引数据结构，以其稳定高效的读写性能著称。与传统的二叉树不同，B 树的每个节点可以存储大量键值，从而降低树的高度，加快搜索和插入元素的速度，并减少磁盘 I/O 操作。B 树的时间复杂度为 O(logN)。

哈希索引

哈希索引是一种基于哈希表的数据结构，哈希值映射到存储桶，存储桶存储数据的偏移量。因此，我们可以根据键值快速查找数据。

跳表

跳表是一种常用的内存索引类型，常用于 SortedSet 中。跳表解决了链表搜索效率低下的问题。每个节点包含多个前向指针，因此我们可以跳过一些节点来加快搜索速度，而不受步长限制。

SSTable

SSTable（SortedStringTable）是 Cassandra 和其他 NoSQL 数据库使用的持久性文件格式。它可以对内存数据进行排序，以便快速访问，并将其存储在磁盘上的一组持久有序不可变的文件中。不可变意味着 SSTable 永远不会被修改，它们稍后会合并到新的 SSTable 中，或者随着数据的更新而被删除。SSTable 与 LSM 树一起使用。

LSM 树

LSM 树（Log-Structured Merge Tree）在 SSTable 的基础上提供一整套存储解决方案。它由两层结构组成：内存中的 memtable 和磁盘上的 SSTable。新数据首先写入 memtable，如果 memtable 过大，就会刷新到磁盘上的 SSTable。各个 SSTable 上可能有重复的键值，在一段时间后会进行合并压缩。由于每个写入请求实际上都只在内存中进行，因此 LSM 树的写入吞吐量明显高于 B 树。

后缀树

后缀树通常用于存储字符串列表，也称为 Trie 的压缩版本。后缀树常用于字符串的搜索和匹配，例如容忍一定输入错误的字符搜索、正则表达式匹配、最长子串问题等。

倒排索引

倒排索引用于高效的文档索引，例如 Lucene。在倒排索引中，索引按单词进行组织，每个单词都指向包含该单词的文档列表。

R 树

R 树用于搜索多维信息，包括地理坐标、矩形、多边形等。我们可以借助这种索引来搜索附近的餐馆、找到最近的加油站、检索附近所有路段等。

选择合适的索引结构

选择合适的索引结构取决于以下因素：

• 数据的类型和大小
• 对数据的典型访问模式（例如范围查询、精确匹配、模糊搜索）
• 数据库的性能目标（例如读取速度、写入吞吐量、存储空间）

没有一种索引结构适用于所有情况。通过了解每种索引结构的优点和缺点，我们可以做出明智的选择，优化数据库的性能。

SQL SERVER中索引类型包括的三种类型分别是哪三种？

三种索引类型分别是：

1、主键索引：不允许具有索引值相同的行，从而禁止重复的索引或键值。系统在创建该索引时检查是否有重复的键值，并在每次使用 INSERT 或 UPDATE 语句添加数据时进行检查。

2、聚集索引：指数据库表行中数据的物理顺序与键值的逻辑（索引）顺序相同。一个表只能有一个聚集索引，因为一个表的物理顺序只有一种情况。

3、非聚集索引：索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同。非聚集索引的叶层不包含数据页。 相反，叶节点包含索引行。

扩展资料

聚集索引对于那些经常要搜索范围值的列特别有效。使用聚集索引找到包含第一个值的行后，便可以确保包含后续索引值的行在物理相邻。

频繁更改的列 这将导致整行移动，因为 SQL Server 必须按物理顺序保留行中的数据值。这一点要特别注意，因为在大数据量事务处理系统中数据是易失的。来自聚集索引的键值由所有非聚集索引作为查找键使用，因此存储在每个非聚集索引的叶条目内。

为什么数据库使用B树索引而非散列索引

数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。 索引的实现通常使用B树及其变种B+树。 在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。 这种数据结构，就是索引。 为表设置索引要付出代价的：一是增加了数据库的存储空间，二是在插入和修改数据时要花费较多的时间(因为索引也要随之变动)。