class RootPageReference extends PageReference {

        public RootPageReference(BTreeStorage bs) {
            super(bs);
        }

        @Override
        public void replacePage(Page newRoot) {
            newRoot.setRef(this);
            if (getPage() != newRoot && newRoot.isNode()) {
                for (PageReference ref : newRoot.getChildren()) {
                    if (ref.getPage() != null && ref.getParentRef() != this)
                        ref.setParentRef(this);
                }
            }
            super.replacePage(newRoot);
        }

        @Override
        public boolean isRoot() {
            return true;
        }
    }

    // btree的root page引用，最开始是一个leaf page，随时都会指向新的page
    private final RootPageReference rootRef;
    private final SchedulerFactory schedulerFactory;

    public BTreeMap(String name, StorageDataType keyType, StorageDataType valueType,
            Map<String, Object> config, AOStorage aoStorage) {
        super(name, keyType, valueType, aoStorage);
        DataUtils.checkNotNull(config, "config");
        schedulerFactory = aoStorage.getSchedulerFactory();
        // 只要包含就为true
        readOnly = config.containsKey(DbSetting.READ_ONLY.name());
        inMemory = config.containsKey(StorageSetting.IN_MEMORY.name());

        this.config = config;
        Object mode = config.get(StorageSetting.PAGE_STORAGE_MODE.name());
        if (mode != null) {
            pageStorageMode = PageStorageMode.valueOf(mode.toString().toUpperCase());
        }
        btreeStorage = new BTreeStorage(this);
        rootRef = new RootPageReference(btreeStorage);
        Chunk lastChunk = btreeStorage.getChunkManager().getLastChunk();
        if (lastChunk != null) {
            size.set(lastChunk.mapSize);
            rootRef.getPageInfo().pos = lastChunk.rootPagePos;
            Page root = rootRef.getOrReadPage();
            // 提前设置，如果root page是node类型，子page就能在Page.getChildPage中找到ParentRef
            rootRef.replacePage(root);
            setMaxKey(lastKey());
        } else {
            Page root = LeafPage.createEmpty(this);
            rootRef.replacePage(root);
        }
    }

    public Page getRootPage() {
        return rootRef.getOrReadPage();
    }

    public PageReference getRootPageRef() {
        return rootRef;
    }

    public void newRoot(Page newRoot) {
        rootRef.replacePage(newRoot);
    }

    public Map<String, Object> getConfig() {
        return config;
    }

    public Object getConfig(String key) {
        return config.get(key);
    }

    public BTreeStorage getBTreeStorage() {
        return btreeStorage;
    }

    public PageStorageMode getPageStorageMode() {
        return pageStorageMode;
    }

    public void setPageStorageMode(PageStorageMode pageStorageMode) {
        this.pageStorageMode = pageStorageMode;
    }

    public SchedulerFactory getSchedulerFactory() {
        return schedulerFactory;
    }

    @Override
    public V get(K key) {
        return binarySearch(key, true);
    }

    public V get(K key, boolean allColumns) {
        return binarySearch(key, allColumns);
    }

    public V get(K key, int columnIndex) {
        return binarySearch(key, new int[] { columnIndex });
    }

    @Override
    public Object[] getObjects(K key, int[] columnIndexes) {
        Page p = getRootPage().gotoLeafPage(key);
        int index = p.binarySearch(key);
        Object v = index >= 0 ? p.getValue(index, columnIndexes) : null;
        return new Object[] { p, v };
    }

    @SuppressWarnings("unchecked")
    private V binarySearch(Object key, boolean allColumns) {
        Page p = getRootPage().gotoLeafPage(key);
        int index = p.binarySearch(key);
        return index >= 0 ? (V) p.getValue(index, allColumns) : null;
    }

    @SuppressWarnings("unchecked")
    private V binarySearch(Object key, int[] columnIndexes) {
        Page p = getRootPage().gotoLeafPage(key);
        int index = p.binarySearch(key);
        return index >= 0 ? (V) p.getValue(index, columnIndexes) : null;
    }

    @Override
    public K firstKey() {
        return getFirstLast(true);
    }

    @Override
    public K lastKey() {
        return getFirstLast(false);
    }

    /**
     * Get the first (lowest) or last (largest) key.
     * 
     * @param first whether to retrieve the first key
     * @return the key, or null if the map is empty
     */
    @SuppressWarnings("unchecked")
    private K getFirstLast(boolean first) {
        if (isEmpty()) {
            return null;
        }
        Page p = getRootPage();
        while (true) {
            if (p.isLeaf()) {
                return (K) p.getKey(first ? 0 : p.getKeyCount() - 1);
            }
            p = p.getChildPage(first ? 0 : getChildPageCount(p) - 1);
        }
    }

    @Override
    public K lowerKey(K key) {
        return getMinMax(key, true, true);
    }

    @Override
    public K floorKey(K key) {
        return getMinMax(key, true, false);
    }

    @Override
    public K higherKey(K key) {
        return getMinMax(key, false, true);
    }

    @Override
    public K ceilingKey(K key) {
        return getMinMax(key, false, false);
    }

    /**
     * Get the smallest or largest key using the given bounds.
     * 
     * @param key the key
     * @param min whether to retrieve the smallest key
     * @param excluding if the given upper/lower bound is exclusive
     * @return the key, or null if no such key exists
     */
    private K getMinMax(K key, boolean min, boolean excluding) {
        return getMinMax(getRootPage(), key, min, excluding);
    }

    @SuppressWarnings("unchecked")
    private K getMinMax(Page p, K key, boolean min, boolean excluding) {<FILL_FUNCTION_BODY>

        if (p.isLeaf()) {
            int x = p.binarySearch(key);
            if (x < 0) {
                x = -x - (min ? 2 : 1);
            } else if (excluding) {
                x += min ? -1 : 1;
            }
            if (x < 0 || x >= p.getKeyCount()) {
                return null;
            }
            return (K) p.getKey(x);
        }
        int x = p.getPageIndex(key);
        while (true) {
            if (x < 0 || x >= getChildPageCount(p)) {
                return null;
            }
            K k = getMinMax(p.getChildPage(x), key, min, excluding);
            if (k != null) {
                return k;
            }
            x += min ? -1 : 1;
        }
    
<methods>public long getAndAddKey(long) ,public com.lealone.storage.type.StorageDataType getKeyType() ,public long getMaxKey() ,public java.lang.String getName() ,public ConcurrentHashMap<java.lang.Object,java.lang.Object> getOldValueCache() ,public com.lealone.storage.Storage getStorage() ,public com.lealone.storage.type.StorageDataType getValueType() ,public long incrementAndGetMaxKey() ,public void setMaxKey(K) <variables>protected final non-sealed com.lealone.storage.type.StorageDataType keyType,protected final java.util.concurrent.atomic.AtomicLong maxKey,protected final non-sealed java.lang.String name,private final ConcurrentHashMap<java.lang.Object,java.lang.Object> oldValueCache,protected final non-sealed com.lealone.storage.Storage storage,protected final non-sealed com.lealone.storage.type.StorageDataType valueType