引子:索引的效率问题 ◆索引( indexing):把一个关键码与它对应 的数据记录的位置相关联 (关键码,指针)对,即(key, pointer) ◆三类索引 线性索引:有序数组、索引顺序文件 树型索引:二叉搜索树(BST)、B/B+树 字符树 ■■■■■■ 散列索引 红黑树之歌 2007年12月25日2时19分 北京大学张铭⊙红黑树2007年12月25日2时19分 北京大学 张铭© 红黑树 2 引子：索引的效率问题 索引( indexing )：把一个关键码与它对应 的数据记录的位置相关联 „ (关键码，指针)对，即(key, pointer) 三类索引 „ 线性索引：有序数组、索引顺序文件 „ 树型索引：二叉搜索树(BST)、 B/B+树 字符树…… „ 散列索引 红黑树之歌