我要招人

去企业版

首页 > 试题广场 >

请你说说数据库索引的底层数据结构

[问答题]

请你说说数据库索引的底层数据结构

大哥们不要卷我

MySQL底层使用的是B+tree存储结构非叶子节点存储索引和下一个子节点的地址叶子结点存储所有的索引和数据

发表于 2022-06-10 14:56:02 回复(1)

牛客624223299号

但MYSQL索引的底层用的并不是红黑树和二叉树。因为二叉树和红黑树在某些场景会暴露出一些缺陷

发表于 2022-05-27 17:39:20 回复(0)

ttccq

数据库索引用的是B+树，它的叶子节点存储所有的数据，并且叶子节点通过指针进行链接，树的查找效率与其高度有关，树的高度越高，查找效率越低，B+树的高度一般在2-4层，这意味着查找到某一键值只需要2-4次IO操作，而且现在的数据库1s中至少可以做100次IO操作，2-4次的IO操作意味着查询时间只需要0.02-0.04s，所以其查找效率很高。

发表于 2022-07-03 20:02:34 回复(0)

狗不言呆子与猫

发表于 2023-03-09 10:14:04 回复(0)

徐涛1

1、索引可选的底层数据结构包括：二叉树、红黑树、hash、B+树。一般选用B+树作为索引，因为： 2、二叉树它具有退化成链表的风险。同时数据量大的时候，树的高度可能会非常的高。 3、红黑树它是一个近似平衡的二叉树，它的树高最高都不会超过2*logn，所以它的性能相对稳定，但是它本质上还是一个二叉树。当数据量多的时候，树的高度可能会非常的高，而数据是存在磁盘上的，也就增加了磁盘的IO次数。 4、hash表通过hash算法快速定位数据，但不适合范围查询，因为需要每个key都进行一次hash。 5、而B+树是一种多叉树，它的非叶子节点只用来存储对应的索引信息，大部分情况下树高都能被控制在2-4层，也就是说只需要最多4次IO就能得到数据，大大降低了磁盘的IO次数。同时它增加了叶子结点间的链接，能保证范围查询时找到起点与终点就能快速取出数据。

发表于 2022-09-26 14:44:32 回复(0)

别打小书包唉

索引可选的底层数据结构有：二叉树、红黑树、hash、B+树，但mysql索引的底层用的并不是二叉树和红黑树。因为二叉树和红黑树在某些场景下都会暴露出一些缺陷。首先，二叉树在某些场景下会退化成链表，而链表的查找需要从头部开始遍历，这就失去了加索引的意义。不适用红黑树的原因是：红黑树作为底层数据结构在面对某些表数据动辄数百万数千万的场景时，会导致索引树的高度很高。索引从根节点开始查找，而如果我们需要查找的数据在底层的叶子结点上，那么树的高度多少，就要进行多少次查找，数据存在磁盘上，访问需要进行磁盘IO，这回导致效率过低。而B+树由B树和索引顺序访问方法演化而来，它是为磁盘或其他直接存取辅助设备设计的一种平衡查找树，在B+树中，所有记录点都是按键值的大小顺序存放在同一层的叶子节点，各叶子节点通过很进行链接。B+树索引在数据库中的一个特点就是高扇出行。

发表于 2022-07-24 17:55:57 回复(0)

深情的三文鱼在写面经

b+树非叶子节点存放的是索引叶子节点存放的是数据

发表于 2023-08-24 14:46:46 回复(0)

钟情于风TuT

底层的数据结构包括: 二叉搜索树，红黑树，hash，b-tree。二叉搜索树当数据从小到达排列时，它的长度依旧很长，不利于查找，而红黑树在数据量庞大的情况下，树的深度很深，磁盘IO效率很低，hash不适合范围查询，而且会产生hash冲突，b-tree叶子节点存储数据和索引，而且使用的是双向链表，查找效率快，树是宽而矮的

发表于 2024-04-03 16:51:38 回复(0)

牛客380258662号

B+树非叶子节点存储key 叶子节点存储数据查找稳定，随着数据量的增加，高度不会有明显的变化叶子节点使用双向链表进行连接，适用于范围查询

发表于 2024-03-17 11:19:37 回复(0)

极客25

B+树，平衡查找树，高扇出性，io少，查询速度稳定，树上所有记录节点都是按键值的大小顺序存放在同一层叶子节点，各个叶子节点通过指针进行连接。

编辑于 2024-02-22 10:43:47 回复(0)

jdasji

数据库索引底层的数据结构是B+树，B+树只有叶子存储数据，非叶子节点只用来存储索引，叶子节点通过指针连接，因此查找数据时遍历叶子节点就可大大提升了查找效率，同时B+树大多在2到4层，减少了磁盘的IO操作，提高了性能

发表于 2023-08-14 14:51:29 回复(0)

自信的大白菜

1.mysql索引的底层用的并不是二叉树和红黑树；
2.二叉树在某些场景下会退化成链表,而链表的查找需要从头部开始遍历,而这就失去了加索引的意义。
3.红黑树作为底层数据结构在面对在些表数据动辄数百万数千万的场景时,会导致索引树的层数很高。索引从根节点开始查找,而如果我们需要查找的数据在底层的叶子节点上,那么树的高度是多少,就要进行多少次查找,数据存在磁盘上,访问需要进行磁盘IO,这会导致效率过低；

4.MYSQL索引的底层用的B+树，B+树是多叉的,可以有效减少磁盘IO次数，同时B+树增加了叶子结点间的连接,能保证范围查询时找到起点和终点后快速取出需要的数据。

5.B+树索引在数据库中的一个特点就是高扇出性,例如在InnoDB存储引擎中,每个页的大小为16KB。在数据库中,B+树的高度一般都在2～4层,这意味着查找某一键值最多只需要2到4次IO操作,这还不错。因为现在一般的磁盘每秒至少可以做100次IO操作,2～4次的IO操作意味着查询时间只需0.02～0.04秒。

编辑于 2023-02-27 12:08:14 回复(0)

牛客131614367号

MySQL和MyISAM数据库索引的底层数据结构都是B+树. 原因: B+树相对红黑树与二叉树而言,在大量数据情况下,B+树的树高会比红黑树和二叉树和红黑树的树高低,每个节点之间按顺序排列,并且每个节点与节点之间增加了链接,可以存放更多的数据在效率上,由于树高较短,在大量数据中查询数据时,需要进行磁盘IO次数,会比红黑树和二叉树少,也就是说查询速度会更快,

发表于 2023-02-21 16:17:44 回复(0)

彭于晏学Java

MYSQL索引的底层用的B+树，B+树是多叉的,可以有效减少磁盘IO次数；同时B+树增加了叶子结点间的连接,能保证范围查询时找到起点和终点后快速取出需要的数据。

发表于 2023-02-01 12:14:00 回复(0)

原来就是你123

1、索引可选的底层数据结构包括：二叉树、红黑树、hash、B-tree 2、Mysql底层用的是B+树。B+树非叶子节点（子节点）上是不存储数据的，仅存储键值；叶子节点上存储键值对（键值和数据）。 3、使用B+树的原因：查找数据的快慢主要取决于树的高度，B+树主要为多叉树的结构，使得大部分情况下树高都能被控制在2-4层。也就是说只需要进行4次IO就能够得到数据，让检索效率得到很好提升 4、二叉树：具有退化成链表的风险。红黑树：面对庞大数据时，树的高度过高;

编辑于 2022-09-15 10:34:54 回复(0)

黄俊忠

mysql的innoDB跟MYISAM的底层都是b+树，不是红黑树跟b树，b+树是多路平衡查找树，整一棵树矮壮，b+树只有在叶子节点存放数据，树就适合遍历，b+树就是在树的基础上，在同一层存放数据，查找数据更加快

发表于 2022-09-03 15:39:26 回复(0)

提交观点

问题信息

数据库

上传者：real19931

难度：

16条回答 91收藏 1738浏览

请你说说数据库索引的底层数据结构

问题信息

热门推荐

相关试题