jiaguofang / b-plus-tree Goto Github PK

I think the delete() implementation might need to be improved. Please see the following failed test:

	@Test
	public void testDelete() throws Exception
	{
		BPlusTree<String,String> t = new BPlusTree<String,String>(4);
		
		t.insert("1", "1");
		t.insert("2", "2");
		t.insert("3", "3");
		t.insert("4", "4");
		
		t.delete("3"); // FIX breaks the tree invariants
		
		t.delete("4"); // throws an exception
	}

这个代码，删除中间值没问题，如果删除的是节点的边界值，会有问题，

插入 [0 ,30]
{[16]}
{[4, 8, 12], [20, 24, 28]}
{[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15]}, {[16, 17, 18, 19], [20, 21, 22, 23], [24, 25, 26, 27], [28, 29, 30]}

删除24
{[16]}
{[4, 8, 12], [20, 24, 28]}
{[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15]}, {[16, 17, 18, 19], [20, 21, 22, 23], [25, 26, 27], [28, 29, 30]}

删除25
{[16]}
{[4, 8, 12], [20, 24, 28]}
{[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15]}, {[16, 17, 18, 19], [20, 21, 22, 23, 26, 27], [26, 27], [28, 29, 30]}

删除26
{[16]}
{[4, 8, 12], [20, 24, 26, 28]}
{[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15]}, {[16, 17, 18, 19], [20, 21, 22, 23], [27], [26, 27, 27], [28, 29, 30]}

实际26还在，还能查出来，主要是因为删除叶子节点最左边（分界点），没有更新父节点对应的数据