鲁道夫·拜尔

简介

鲁道夫·拜尔(Rudolf Bayer,1939 年生)是德国计算机科学家,慕尼黑工业大学信息学教授。他最著名的贡献是 1972 年与 Edward McCreight 在波音研究实验室合作发表的 B 树(B-tree),这一结构成为其后数十年几乎所有磁盘数据库索引的基础。

B 树的意义

B 树是一种多路平衡查找树,节点大小与磁盘块对齐,树高极低,使得在机械磁盘上以极少的 IO 完成查找、插入与删除。其变体 B+ 树(叶子链表化、内部节点只存键)成为关系数据库索引的事实标准。论文标题中"B"的含义作者从未正式解释,常见猜测包括 Balanced、Boeing 或 Bayer。

其他贡献

拜尔于 1972 年还提出对称二叉 B 树(symmetric binary B-tree),后被 Guibas 与 Sedgewick 重新表述为红黑树。他在数据库并发控制、UB 树(结合 Z 序曲线的多维索引)等方向也有重要工作,曾获 2001 年 ACM SIGMOD 创新奖。