Java Lock a range of array -

i'm trying implement array-based lock-free binary search tree. in order make work concurrently, should lock range of array in method. how can achieve it?

public int getindex(int data){         int index = 1;         while(index<this.capacity && this.array[index] != 0){             if(data < this.array[index])                 index = index *2;             else if (data> this.array[index])                 index = index * 2 + 1;             else                 break;         }          if(index >= this.capacity)             return -1;         else             return index;     }    public void insert(int data){         int index = this.getindex(data);         if (index == -1) {             this.reallocate();             index = this.getindex(data);             this.array[index] = data;          }         else {             if (this.array[index] == 0)                 this.array[index] = data;         }      } 

i'm getting put data in getindex method , insert it. so, in getindex should lock part of array i'm iterating.

if tree not balance after insertions, can grow huge sizes (inserting integers 1 100, in order, require array of size 2^100; don't have ram). assume tree rebalancing keep memory sizes in check.

to find key, need traverse root , log(size-of-array) additional nodes. if there rebalancing involved, nodes in path, root, may re-shuffled. since root can change, no 2 writes can happen @ same time (where write insertion or deletion). additionally, rebalancing involves moving chunks of array around; replacing root requires moving halfs-of-the-whole-tree around, , expensive. doubt that, being worried performance enough consider partially-locking parts of backing array, want dragged down expensive, o(n) operations on tree.

reads can lot more concurrent: go down tree once, , don't rebalance upwards (if don't mind running out of memory, non-rebalancing tree exhibits writes, excluding deletes). there can number of concurrent read operations working @ same time. , can add things without worrying bad reads @ - reads either find looking for, or may return "not found" if got there late while thread writing them in. use volatile array though, or other threads may never see changes.

there remains special case concerning non-rebalancing tree , delete(). deletes (may) affect nodes outside direct downwards path (see pictures here). moving (sub)trees around expensive (linear) array; bits intend move need locked out, because during move invalid reads made. still, suspect not going implement delete() due bad efficiency.