9.1.3分块查找 又称索引顺序查找 一介于顺序查和折半查找之间。适合于关键字分块有序 typedefstruct{ KeyType key; int stadr; indexltem; typedefstruct{ indexItem *elem; int length; }indexTable; -Search Idx(SSTable ST,indexTable ID,KeyT kval) -设索引长度b,顺序表长度为n,则： ASLidx=ASL(b)+ASL(n/b)~log2(b+1)-1+(n/b+1)/2 ypb@ustc.edu.cn 6 中国科学技术大学ypb@ustc.edu.cn 6 中国科学技术大学 • 又称索引顺序查找 – 介于顺序查和折半查找之间。适合于关键字分块有序 typedefstruct { KeyType key; int stadr; }indexItem; typedefstruct{ indexItem *elem; int length; }indexTable; – 算法Search_Idx(SSTable ST,indexTable ID, KeyT kval) – 设索引长度b，顺序表长度为n，则： ASLidx=ASL(b)+ASL(n/b)≈log2 (b+1)-1+(n/b+1)/2 9.1.3分块查找