Speed up b-tree

Question

I wrote a simple implementation of a b-tree, and the problem is that it is too slow (tl9 on codeforces). What should i change to speed up this tree?

The memory limit problem can be easily fixed by increasing the constant b, but then there are time limit problems.

    class BtreeSimple
    {
        public Bnode root = new Bnode(true);
        private static int counter;
 
        public void Add(int key)
        {
            var (overkey, overflow, overvalue) = root.Insert(key, counter);
            counter++;
            if (overflow == null)
                return;
            root = new Bnode(false) {Count = 1, Keys = {[0] = overkey}, Vals = {[0] = overvalue}, Kids = {[0] = root, [1] = overflow}};
        }
    }
 
    class Bnode
    {
        const int b = 16;
        public int Count;
        public int[] Keys = new int[2 * b + 1];
        public Bnode[] Kids;
        public Bnode(bool leaf) => Kids = leaf ? null : new Bnode[2 * b + 2];
        public int[] Vals = new int[2 * b + 1];
 
        public (int, Bnode, int) Insert(int key, int value)
        {
            var i = GetKeyPosition(key);
            if (Kids == null) return InsertAt(i, key, null, value);
            var (overkey, overflow, overvalue) = Kids[i].Insert(key, value);
            return overflow == null ? (0, null, 0) : InsertAt(i, overkey, overflow, overvalue);
        }
 
        private int GetKeyPosition(int key)
        {
            var i = 0;
            while (i < Count && Keys[i] < key)
                i++;
            return i;
        }
 
        private (int, Bnode, int) InsertAt(int i, int key, Bnode keyNode, int value)
        {
            Array.Copy(Keys, i, Keys, i + 1, Count - i);
            Keys[i] = key;
            Vals[i] = value;
            if (keyNode != null)
            {
                Array.Copy(Kids, i + 1, Kids, i + 2, Count - i);
                Kids[i + 1] = keyNode;
            }
            return ++Count <= 2 * b ? (0, null, 0) : Split();
        }
 
        private (int, Bnode, int) Split()
        {
            var split = new Bnode(Kids == null) { Count = b };
            Array.Copy(Keys, b + 1, split.Keys, 0, b);
            Array.Copy(Vals, b + 1, split.Vals, 0, b);
            if (Kids != null)
                Array.Copy(Kids, b + 1, split.Kids, 0, b + 1);
            Count = b;
            return (Keys[b], split, Vals[b]);
        }
 
        public int FindNearest(int key)
        {
            var i = GetKeyPosition(key);
            if (Keys[i] == key)
                return Vals[i];
            if (Kids != null)
                return Kids[i].FindNearest(key);
            if (i >= Count)
                return Vals[i - 1]+1;
            if (Keys[i] < key)
                return Vals[i] + 1;
            return Vals[i];
        }
    }

We have a sorted array (for example arr = [8, 9, 10, 11, 15, 17, 20]) and keys (for example keys = [7, 10, 21, 20]). The task is to tell how many keys from arr are less than keys[i] for each i. For this purpose I made a methdod "FindNearest". Everything else in the code is just pure b-tree.