数据库索引只能用 B 树吗?
创始人
2025-07-05 18:10:04
0


今天我们来聊聊数据库索引。

无论数据存储于磁盘还是内存,我们都需要有一种高效的数据结构来访问和获取数据。

那么我们应该选用哪一种索引结构呢?我们需要考虑如下几个因素:

  • 数据存储于内存还是磁盘?
  • 数据格式和结构是怎样的?是字符串,数字,还是地理坐标?
  • 搜索时是否需要精确匹配?是否需要容忍一定的输入错误?
  • 系统是读操作多还是写操作多?

我们来看看 8 种常用的数据库索引结构。

图片图片

B 树

B 树/B+ 树作为最流行的数据库索引数据结构,是基于磁盘的解决方案,其读/写性能稳定。不同于传统的二叉树,B 树的单个节点中可以存储大量的键值,这样树的高度较低,可以加快搜索和插入元素的速度,减少磁盘的 I/O 操作。B 树的时间复杂度为 O(logN)。

Hash Index(哈希索引)

Map 数据结构的常用实现。哈希值映射到存储桶,该存储桶存储数据的偏移值。这样我们可以根据键值很快地查找数据。

Skiplist(跳表)

一种常见的内存索引类型,在 Redis SortedSet 中使用。跳表解决了链表搜索效率低下的问题。每个节点都包含几个前向指针,因此我们不被遍历过程中的步长所限制,可以跳过一些节点来加快搜索速度。

SSTable(Sorted String Table)

SSTable 是 Apache Cassandra 和其他 NoSQL 数据库使用的一种持久性文件格式。它可以对 memtable 里的内存数据进行排序以便快速访问,并将其存储在磁盘上的持久有序、不可变的一组文件中。不可变意味着 SSTables 永远不会被修改。它们稍后会合并到新的 SSTables 中,或者随着数据的更新而被删除。SSTable 与 LSM Tree 一起使用。与 B 树相比,这种结构对于写入量大、快速增长的超大数据集效率更高。

LSM 树(Log-Structured Merge Tree)

LSM Tree 在 SSTable 的基础上提供一整套存储解决方案。它由两层结构组成:memtable (内存)和 SSTable(磁盘)。新数据先写入 memtable 中,如果 memtable 过大,那就会 flush 到磁盘的 SSTable 上。各个 SSTable 上会有重复的键值,在一段时间后会进行合并压缩。我们可以看到,每个写入请求实际上都只在内存中进行,所以 LSM Tree 的写入吞吐量明显高于 B Tree。

Suffix Tree(后缀树)

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

Inverted Index(倒排索引)

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

R 树

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

相关内容

热门资讯

如何允许远程连接到MySQL数... [[277004]]【51CTO.com快译】默认情况下,MySQL服务器仅侦听来自localhos...
如何利用交换机和端口设置来管理... 在网络管理中,总是有些人让管理员头疼。下面我们就将介绍一下一个网管员利用交换机以及端口设置等来进行D...
施耐德电气数据中心整体解决方案... 近日,全球能效管理专家施耐德电气正式启动大型体验活动“能效中国行——2012卡车巡展”,作为该活动的...
20个非常棒的扁平设计免费资源 Apple设备的平面图标PSD免费平板UI 平板UI套件24平图标Freen平板UI套件PSD径向平...
德国电信门户网站可实时显示全球... 德国电信周三推出一个门户网站,直观地实时提供其安装在全球各地的传感器网络检测到的网络攻击状况。该网站...
为啥国人偏爱 Mybatis,... 关于 SQL 和 ORM 的争论,永远都不会终止,我也一直在思考这个问题。昨天又跟群里的小伙伴进行...
《非诚勿扰》红人闫凤娇被曝厕所... 【51CTO.com 综合消息360安全专家提醒说,“闫凤娇”、“非诚勿扰”已经被黑客盯上成为了“木...
2012年第四季度互联网状况报... [[71653]]  北京时间4月25日消息,据国外媒体报道,全球知名的云平台公司Akamai Te...