private int getIndexByKey(String key) {
    // TODO: before leaf node implement cascade delete,
    //  RecordDuplicatedException will only be thrown from leaf node

    // notice that memberNum always bigger than 2 in a valid Internal Segment
    if (memberNum == 1 || key.compareTo(getKeyByIndex(1)) < 0) {
      return 0;
    } else if (key.compareTo(getKeyByIndex(memberNum - 1)) >= 0) {
      return memberNum - 1;
    }

    int head = 1;
    int tail = memberNum - 1;
    int pivot = (head + tail) / 2;

    // breaking condition: pivot smaller than key, but (pivot+1) bigger than key
    while (!((key.compareTo(getKeyByIndex(pivot)) >= 0)
        && (key.compareTo(getKeyByIndex(pivot + 1)) < 0))) {
      if (key.compareTo(getKeyByIndex(pivot)) < 0) {
        tail = pivot;
      } else if (key.compareTo(getKeyByIndex(pivot + 1)) == 0) {
        return pivot + 1;
      } else if (key.compareTo(getKeyByIndex(pivot + 1)) > 0) {
        head = pivot;
      }

      // it can be proved that pivot <= n-2
      pivot = (head + tail) / 2;
    }
    return pivot;
  }
Find suitable position to find or insert key. Notice that index ranges from 0 to memberNum-1.

@param key to be searched or inserted.
@return position where the key is the biggest one smaller or equals to parameter.
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/schemaengine/schemaregion/mtree/impl/pbtree/schemafile/InternalPage.java