Branch-and-Bound (B&B) algorithm is one of the fundamental methods for combinatorial optimization problems. The running time is dominated by the data structure used to implement B&B algorithm for the given problem and the related branching strategy. In this paper, the data structure called Cubeheap and the related algorithms (INSERT and DELETE) are discussed. The lower bound Ω(m+hlogh) of the running time for general B&B algorithm is proposed by constructing the mapping between the B&B procedure and the sorting procedure, where m is the number of the evaluated nodes and h is the number of the expanded nodes. According to the lower bound, Cubeheap is the near-optimal data structure to implement the general B&B algorithm. The experimental results for a concrete combinatorial optimization problem, Job-assignment, are obtained by running the B&B algorithm with the Cubeheap. The method to improve the balance of the Cubeheap is also proposed.