Index: disksegment.go
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
--- disksegment.go	(date 1535771631000)
+++ disksegment.go	(date 1535771665000)
@@ -34,6 +34,13 @@
 	dataFile  *os.File
 	compare   KeyCompare
 	id        uint64
+	keyIndex  []keyIndexEntry // nil for segments loaded during initial open
+}
+
+// currently tracks every 16th block, for more efficient binary searching
+type keyIndexEntry struct {
+	key	[]byte
+	block int
 }
 
 type diskSegmentIterator struct {
@@ -70,7 +77,7 @@
 			id := getSegmentID(file.Name())
 			keyFilename := filepath.Join(directory, base+".keys."+strconv.FormatUint(id, 10))
 			dataFilename := filepath.Join(directory, base+".data."+strconv.FormatUint(id, 10))
-			segments = append(segments, newDiskSegment(keyFilename, dataFilename, compare))
+			segments = append(segments, newDiskSegment(keyFilename, dataFilename, compare,nil)) // don't have keyIndex
 		}
 	}
 	sort.Slice(segments, func(i, j int) bool {
@@ -91,7 +98,7 @@
 	return 0
 }
 
-func newDiskSegment(keyFilename, dataFilename string, compare KeyCompare) segment {
+func newDiskSegment(keyFilename, dataFilename string, compare KeyCompare,keyIndex []keyIndexEntry) segment {
 
 	segmentID := getSegmentID(keyFilename)
 
@@ -115,6 +122,7 @@
 	ds.keyBlocks = (fi.Size()-1)/keyBlockSize + 1
 	ds.compare = compare
 	ds.id = segmentID
+	ds.keyIndex = keyIndex
 
 	return ds
 }
@@ -244,7 +252,21 @@
 func binarySearch(ds *diskSegment, key []byte) (offset int64, len uint32, err error) {
 	buffer := make([]byte, keyBlockSize)
 
-	block, err := binarySearch0(ds, 0, ds.keyBlocks-1, key, buffer)
+	var lowblock int64 = 0
+	highblock := ds.keyBlocks-1
+
+	if ds.keyIndex!=nil { // we have memory index, so narrow block range down
+		block:=sort.Search(len(ds.keyIndex), func(i int) bool {
+			return ds.compare.Less(key,ds.keyIndex[i].key)
+		})
+		lowblock = int64(block-keyIndexInterval)
+		highblock = int64(block)
+		if lowblock<0 {
+			lowblock = 0
+		}
+	}
+
+	block, err := binarySearch0(ds,lowblock,highblock, key, buffer)
 	if err != nil {
 		return 0, 0, err
 	}
Index: diskio.go
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
--- diskio.go	(date 1535771631000)
+++ diskio.go	(date 1535771781000)
@@ -17,6 +17,7 @@
 const compressedBit uint16 = 0x8000
 const maxPrefixLen uint16 = 0xFF ^ 0x80
 const maxCompressedLen uint16 = 0xFF
+const keyIndexInterval int = 16 // record every 16th block
 
 var emptySegment = errors.New("empty segment")
 
@@ -65,7 +66,7 @@
 	keyFilenameTmp := keyFilename + ".tmp"
 	dataFilenameTmp := dataFilename + ".tmp"
 
-	err := writeSegmentFiles(keyFilenameTmp, dataFilenameTmp, itr)
+	keyIndex,err := writeSegmentFiles(keyFilenameTmp, dataFilenameTmp, itr)
 	if err != nil {
 		os.Remove(keyFilenameTmp)
 		os.Remove(dataFilenameTmp)
@@ -75,22 +76,24 @@
 	os.Rename(keyFilenameTmp, keyFilename)
 	os.Rename(dataFilenameTmp, dataFilename)
 
-	return newDiskSegment(keyFilename, dataFilename, compare), nil
+	return newDiskSegment(keyFilename, dataFilename, compare, keyIndex), nil
 }
 
-func writeSegmentFiles(keyFName, dataFName string, itr LookupIterator) error {
+func writeSegmentFiles(keyFName, dataFName string, itr LookupIterator) ([]keyIndexEntry,error) {
+
+	keyIndex:=[]keyIndexEntry{}
 
 	keyF, err := os.OpenFile(keyFName, os.O_CREATE|os.O_WRONLY, os.ModePerm)
 	if err != nil {
 		fmt.Println("unable to create key segments", err)
-		return err
+		return nil,err
 	}
 	defer keyF.Close()
 
 	dataF, err := os.OpenFile(dataFName, os.O_CREATE|os.O_WRONLY, os.ModePerm)
 	if err != nil {
 		fmt.Println("unable to create data file", err)
-		return err
+		return nil,err
 	}
 	defer dataF.Close()
 
@@ -100,6 +103,7 @@
 	var dataOffset int64
 	var keyBlockLen int
 	var keyCount = 0
+	var block = 0
 
 	var zeros = make([]byte, keyBlockSize)
 
@@ -122,6 +126,11 @@
 			prevKey = nil
 		}
 
+		if keyBlockLen==0 && block%keyIndexInterval==0 {
+			keyIndex = append(keyIndex,keyIndexEntry{key,block})
+			block++
+		}
+
 		var dataLen uint32
 		if value == nil {
 			dataLen = 0
@@ -169,14 +178,14 @@
 	dataW.Flush()
 
 	if keyCount == 0 {
-		return emptySegment
+		return nil,emptySegment
 	}
 
-	return nil
+	return keyIndex,nil
 
 failed:
 	fmt.Println("unable to write segment", err)
-	return err
+	return nil,err
 }
 
 func calculatePrefixLen(prevKey []byte, key []byte) int {