知识卡片
B+树的叶子链表
B+ 树是[[B树索引结构与效率]]的变种,改动在于数据存在哪一层:B 树每个关键字都关联数据指针,B+ 树把数据关联全部下沉到叶子节点,非叶子节点的关键字只作为子树最小关键字的路标。好处有二:非叶子节点不存数据指针,能容纳更多关键字,树更矮;叶子节点从左到右用指针串成有序链表。所以范围查询和按序扫描全表在 B+ 树上明显更快:B 树要在树中反复定位,B+ 树只需一次定位加一次线性遍历。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《数据库原理(微课版)》第9章《数据库存储与索引》9.2.3节"B树
索引"(源文件:_epub-src/index_split_006.html)
- 结论依据:原文明确"B+树……在B树的基础上,它增加了非叶子节点数据
在叶子节点中的存储……每个关键字是它右侧指针所指向子树中的最小
关键字……B+树指向关键字所对应数据的指针都在叶子节点上,非叶子
节点不需要保存指向数据的指针""若在B+树的叶子节点层从最左节点开始,
每个节点增加一个指向其相邻右节点的指针,可形成一个关键字有序排列
的链表。若需要按关键字顺序扫描一张数据表,也可以利用这个链表进行",
因此可以推出B+树叶子链表结构支持高效范围查询和顺序扫描的结论。
- 原始内容:B+树指向关键字所对应数据的指针都在叶子节点上,非叶子节点不需要保存指向数据的指针……若在B+树的叶子节点层从最左节点开始,每个节点增加一个指向其相邻右节点的指针,可形成一个关键字有序排列的链表。