高手指教一下索引实现的基础 － B+树数据结构吧！

Question

:-( 建议去 expert.csdn.net -> 专题开发 -> 数据结构与算法 提问吧. :-)

Answer 1

B-Tree---就是平衡树。
B-tree T 的定義: 
  T 是一棵 (2t)-ary search tree. 
  每個 internal node 至少有 t 個 children. root 例外, 它至少要有 2 個 children. 
  所有的 leaves 都在同一層. 
---------------------------------------
B-Tree索引是最普通的索引，缺省条件下建立的索引就是这种类型的索引。B-Tree索引可以是唯一或非唯一的，可以是单一的（基于一列）或连接的（多列）。B-Tree索引在检索高基数数据列（高基数数据列是指该列有很多不同的值）时提供了最好的性能。对于取出较小的数据B-Tree索引比全表检索提供了更有效的方法。但当检查的范围超过表的10%时就不能提高取回数据的性能。正如名字所暗示的那样，B-Tree索引是基于二元树的，由枝干块（branch block)和树叶块（leaf block)组成,枝干块包含了索引列（关键字）和另一索引的地址。树叶块包含了关键字和给表中每个匹配行的ROWID。

Answer 2

http://tmtc.edu.tw/~lai/af-teach/af-algorithm-DS/DSinjava/
可以下载关于b-tree的幻灯片