private IndexValue findKey(StoreKey key, FileSpan fileSpan, EnumSet<IndexEntryType> types,
      ConcurrentSkipListMap<Offset, IndexSegment> indexSegments) throws StoreException {
    if (fileSpan != null && fileSpan.isEmpty()) {
      return null;
    }
    IndexValue latest = null;
    IndexValue retCandidate = null;
    final Timer.Context context = metrics.findTime.time();
    try {
      ConcurrentNavigableMap<Offset, IndexSegment> segmentsMapToSearch;
      if (fileSpan == null) {
        logger.trace("Searching for {} in the entire index", key);
        segmentsMapToSearch = indexSegments.descendingMap();
      } else {
        logger.trace("Searching for {} in index with filSpan ranging from {} to {}", key, fileSpan.getStartOffset(),
            fileSpan.getEndOffset());
        Offset fromIndexOffset = indexSegments.floorKey(fileSpan.getStartOffset());
        Offset toIndexOffset = indexSegments.lowerKey(fileSpan.getEndOffset());
        if (toIndexOffset == null) {
          segmentsMapToSearch = new ConcurrentSkipListMap<>();
        } else {
          segmentsMapToSearch =
              indexSegments.subMap(fromIndexOffset == null ? indexSegments.firstKey() : fromIndexOffset, true,
                  toIndexOffset, true).descendingMap();
        }
        metrics.segmentSizeForExists.update(segmentsMapToSearch.size());
      }
      int segmentsSearched = 0;
      for (Map.Entry<Offset, IndexSegment> entry : segmentsMapToSearch.entrySet()) {
        segmentsSearched++;
        logger.trace("Index : {} searching index with start offset {}", dataDir, entry.getKey());
        NavigableSet<IndexValue> values = entry.getValue().find(key);
        if (values != null) {
          Iterator<IndexValue> it = values.descendingIterator();
          while (it.hasNext()) {
            IndexValue value = it.next();
            if (fileSpan != null) {
              // Start <= value.offset < End
              if (value.getOffset().compareTo(fileSpan.getEndOffset()) >= 0) {
                continue;
              }
              if (value.getOffset().compareTo(fileSpan.getStartOffset()) < 0) {
                break;
              }
            }
            if (latest == null) {
              latest = value;
            }
            logger.trace("Index : {} found value offset {} size {} ttl {}", dataDir, value.getOffset(), value.getSize(),
                value.getExpiresAtMs());
            if (types.contains(IndexEntryType.DELETE) && value.isDelete()) {
              retCandidate = value;
              break;
            } else if (types.contains(IndexEntryType.UNDELETE) && value.isUndelete()) {
              retCandidate = value;
              break;
            } else if (types.contains(IndexEntryType.TTL_UPDATE) && !value.isDelete() && !value.isUndelete()
                && value.isTtlUpdate()) {
              retCandidate = value;
              break;
            } else if (types.contains(IndexEntryType.PUT) && value.isPut()) {
              retCandidate = value;
              break;
            }
            // note that it is not possible for a TTL update record to exist for a key but not have a PUT or DELETE
            // record.
          }
          if (retCandidate != null) {
            // merge entries if required to account for updated fields
            if (latest.isTtlUpdate() && !retCandidate.isTtlUpdate()) {
              retCandidate = new IndexValue(retCandidate.getOffset().getName(), retCandidate.getBytes(),
                  retCandidate.getFormatVersion());
              retCandidate.setFlag(IndexValue.Flags.Ttl_Update_Index);
              retCandidate.setExpiresAtMs(latest.getExpiresAtMs());
            }
            break;
          }
        }
      }
      metrics.segmentsAccessedPerBlobCount.update(segmentsSearched);
    } finally {
      context.stop();
    }
    if (retCandidate != null) {
      logger.trace("Index : {} Returning value offset {} size {} ttl {}", dataDir, retCandidate.getOffset(),
          retCandidate.getSize(), retCandidate.getExpiresAtMs());
    }
    return retCandidate;
  }
Finds the latest {@link IndexValue} associated with the {@code key} that matches any of the provided {@code types}
if present in the index within the given {@code fileSpan}.
@param key the {@link StoreKey} whose {@link IndexValue} is required.
@param fileSpan {@link FileSpan} which specifies the range within which search should be made
@param types the types of {@link IndexEntryType} to look for. The latest entry matching one of the types will be
             returned
@param indexSegments the map of index segment start {@link Offset} to {@link IndexSegment} instances
@return The latest {@link IndexValue} for {@code key} conforming to one of the types {@code types} - if one exists
within the {@code fileSpan}, {@code null} otherwise.
@throws StoreException
ambry-store/src/main/java/com/github/ambry/store/PersistentIndex.java